From 05a77f3559bff860de052d23fb8cdefdadd53b3c Mon Sep 17 00:00:00 2001 From: dgp Date: Mon, 1 Feb 2016 21:39:44 +0000 Subject: Backout the contributed patch memaccounting from Postgres since it changes the protections incompatibly and causes established tests to crash. --- generic/regc_nfa.c | 84 +++++++++++++++++++++++++++++++++++++++++++++--------- generic/regcomp.c | 2 -- generic/regerrs.h | 2 +- generic/regex.h | 2 +- generic/regguts.h | 16 +++++------ tests/regexp.test | 2 +- 6 files changed, 80 insertions(+), 28 deletions(-) diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c index 6280e5e..d155b23 100644 --- a/generic/regc_nfa.c +++ b/generic/regc_nfa.c @@ -62,6 +62,7 @@ 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. */ @@ -89,6 +90,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 *); */ @@ -124,20 +180,20 @@ 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; } else { - if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE) { - NERR(REG_ETOOBIG); - return NULL; - } s = (struct state *) MALLOC(sizeof(struct state)); if (s == NULL) { NERR(REG_ESPACE); return NULL; } - nfa->v->spaceused += sizeof(struct state); s->oas.next = NULL; s->free = NULL; s->noas = 0; @@ -161,6 +217,12 @@ newstate( } s->prev = nfa->slast; nfa->slast = s; + + /* + * Track the current size and the parent size. + */ + + IncrementSize(nfa); return s; } @@ -231,6 +293,7 @@ freestate( s->prev = NULL; s->next = nfa->free; /* don't delete it, put it on the free list */ nfa->free = s; + DecrementSize(nfa); } /* @@ -249,13 +312,11 @@ destroystate( for (ab=s->oas.next ; ab!=NULL ; ab=abnext) { abnext = ab->next; FREE(ab); - nfa->v->spaceused -= sizeof(struct arcbatch); } s->ins = NULL; s->outs = NULL; s->next = NULL; FREE(s); - nfa->v->spaceused -= sizeof(struct state); } /* @@ -378,19 +439,14 @@ allocarc( */ if (s->free == NULL) { - struct arcbatch *newAb; + struct arcbatch *newAb = (struct arcbatch *) + MALLOC(sizeof(struct arcbatch)); int i; - if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE) { - NERR(REG_ETOOBIG); - return NULL; - } - newAb = (struct arcbatch *) MALLOC(sizeof(struct arcbatch)); if (newAb == NULL) { NERR(REG_ESPACE); return NULL; } - nfa->v->spaceused += sizeof(struct arcbatch); newAb->next = s->oas.next; s->oas.next = newAb; diff --git a/generic/regcomp.c b/generic/regcomp.c index 8287b7e..fda40e0 100644 --- a/generic/regcomp.c +++ b/generic/regcomp.c @@ -227,7 +227,6 @@ struct vars { struct cvec *cv2; /* utility cvec */ struct subre *lacons; /* lookahead-constraint vector */ int nlacons; /* size of lacons */ - size_t spaceused; /* approx. space used for compilation */ }; /* parsing macros; most know that `v' is the struct vars pointer */ @@ -337,7 +336,6 @@ compile( v->cv2 = NULL; v->lacons = NULL; v->nlacons = 0; - v->spaceused = 0; re->re_magic = REMAGIC; re->re_info = 0; /* bits get set during parse */ re->re_csize = sizeof(chr); diff --git a/generic/regerrs.h b/generic/regerrs.h index ee203d5..72548ff 100644 --- a/generic/regerrs.h +++ b/generic/regerrs.h @@ -16,5 +16,5 @@ { REG_INVARG, "REG_INVARG", "invalid argument to regex function" }, { REG_MIXED, "REG_MIXED", "character widths of regex and string differ" }, { REG_BADOPT, "REG_BADOPT", "invalid embedded option" }, -{ REG_ETOOBIG, "REG_ETOOBIG", "regular expression is too complex" }, +{ REG_ETOOBIG, "REG_ETOOBIG", "nfa has too many states" }, { REG_ECOLORS, "REG_ECOLORS", "too many colors" }, diff --git a/generic/regex.h b/generic/regex.h index b5b11bd..b5dce50 100644 --- a/generic/regex.h +++ b/generic/regex.h @@ -277,7 +277,7 @@ typedef struct { #define REG_INVARG 16 /* invalid argument to regex function */ #define REG_MIXED 17 /* character widths of regex and string differ */ #define REG_BADOPT 18 /* invalid embedded option */ -#define REG_ETOOBIG 19 /* regular expression is too complex */ +#define REG_ETOOBIG 19 /* nfa has too many states */ #define REG_ECOLORS 20 /* too many colors */ /* two specials for debugging and testing */ #define REG_ATOI 101 /* convert error-code name to number */ diff --git a/generic/regguts.h b/generic/regguts.h index 72bdcb3..7ed8ec1 100644 --- a/generic/regguts.h +++ b/generic/regguts.h @@ -307,6 +307,9 @@ struct nfa { struct colormap *cm; /* the color map */ color bos[2]; /* colors, if any, assigned to BOS and BOL */ color eos[2]; /* colors, if any, assigned to EOS and EOL */ + size_t size; /* Current NFA size; differs from nstates as + * it also counts the number of states created + * by children of this state. */ struct vars *v; /* simplifies compile error reporting */ struct nfa *parent; /* parent NFA, if any */ }; @@ -336,16 +339,11 @@ struct cnfa { #define NULLCNFA(cnfa) ((cnfa).nstates == 0) /* - * This symbol limits the transient heap space used by the regex compiler, - * and thereby also the maximum complexity of NFAs that we'll deal with. - * Currently we only count NFA states and arcs against this; the other - * transient data is generally not large enough to notice compared to those. - * Note that we do not charge anything for the final output data structures - * (the compacted NFA and the colormap). + * Used to limit the maximum NFA size to something sane. [Bug 1810264] */ -#ifndef REG_MAX_COMPILE_SPACE -#define REG_MAX_COMPILE_SPACE \ - (100000 * sizeof(struct state) + 100000 * sizeof(struct arcbatch)) + +#ifndef REG_MAX_STATES +# define REG_MAX_STATES 100000 #endif /* diff --git a/tests/regexp.test b/tests/regexp.test index 7878d41..362f425 100644 --- a/tests/regexp.test +++ b/tests/regexp.test @@ -716,7 +716,7 @@ test regexp-22.4 {Bug 3606139} -setup { [a 668]([a 55])[a 668]([a 55])[a 668]([a 55])[a 511]] {}] a } -cleanup { rename a {} -} -returnCodes 1 -match glob -result {couldn't compile regular expression pattern: *} +} -returnCodes 1 -result {couldn't compile regular expression pattern: nfa has too many states} test regexp-22.5 {Bug 3610026} -setup { set e {} set cp 99 -- cgit v0.12