2 files changed, 42 insertions, 14 deletions

diff --git a/lib/libc/regex/engine.c b/lib/libc/regex/engine.c
index 35bcb5a83801c..0898a32efb376 100644
--- a/lib/libc/regex/engine.c
+++ b/lib/libc/regex/engine.c
@@ -107,10 +107,11 @@ extern "C" {
 /* === engine.c === */
 static int matcher(struct re_guts *g, char *string, size_t nmatch, regmatch_t pmatch[], int eflags);
 static char *dissect(struct match *m, char *start, char *stop, sopno startst, sopno stopst);
-static char *backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst, sopno lev);
+static char *backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst, sopno lev, int);
 static char *fast(struct match *m, char *start, char *stop, sopno startst, sopno stopst);
 static char *slow(struct match *m, char *start, char *stop, sopno startst, sopno stopst);
 static states step(struct re_guts *g, sopno start, sopno stop, states bef, wint_t ch, states aft);
+#define MAX_RECURSION	100
 #define	BOL	(OUT-1)
 #define	EOL	(BOL-1)
 #define	BOLEOL	(BOL-2)
@@ -302,7 +303,7 @@ int eflags;
 				return(REG_ESPACE);
 			}
 			NOTE("backref dissect");
-			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
+			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
 		}
 		if (dp != NULL)
 			break;
@@ -325,7 +326,7 @@ int eflags;
 			}
 #endif
 			NOTE("backoff dissect");
-			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
+			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
 		}
 		assert(dp == NULL || dp == endp);
 		if (dp != NULL)		/* found a shorter one */
@@ -557,13 +558,14 @@ sopno stopst;
  ==	char *stop, sopno startst, sopno stopst, sopno lev);
  */
 static char *			/* == stop (success) or NULL (failure) */
-backref(m, start, stop, startst, stopst, lev)
+backref(m, start, stop, startst, stopst, lev, rec)
 struct match *m;
 char *start;
 char *stop;
 sopno startst;
 sopno stopst;
 sopno lev;			/* PLUS nesting level */
+int rec;
 {
 	int i;
 	sopno ss;		/* start sop of current subRE */
@@ -678,6 +680,8 @@ sopno lev;			/* PLUS nesting level */
 			return(NULL);
 		assert(m->pmatch[i].rm_so != -1);
 		len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
+		if (len == 0 && rec++ > MAX_RECURSION)
+			return(NULL);
 		assert(stop - m->beginp >= len);
 		if (sp > stop - len)
 			return(NULL);	/* not enough left to match */
@@ -686,28 +690,28 @@ sopno lev;			/* PLUS nesting level */
 			return(NULL);
 		while (m->g->strip[ss] != SOP(O_BACK, i))
 			ss++;
-		return(backref(m, sp+len, stop, ss+1, stopst, lev));
+		return(backref(m, sp+len, stop, ss+1, stopst, lev, rec));
 		break;
 	case OQUEST_:		/* to null or not */
-		dp = backref(m, sp, stop, ss+1, stopst, lev);
+		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 		if (dp != NULL)
 			return(dp);	/* not */
-		return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev));
+		return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec));
 		break;
 	case OPLUS_:
 		assert(m->lastpos != NULL);
 		assert(lev+1 <= m->g->nplus);
 		m->lastpos[lev+1] = sp;
-		return(backref(m, sp, stop, ss+1, stopst, lev+1));
+		return(backref(m, sp, stop, ss+1, stopst, lev+1, rec));
 		break;
 	case O_PLUS:
 		if (sp == m->lastpos[lev])	/* last pass matched null */
-			return(backref(m, sp, stop, ss+1, stopst, lev-1));
+			return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
 		/* try another pass */
 		m->lastpos[lev] = sp;
-		dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev);
+		dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec);
 		if (dp == NULL)
-			return(backref(m, sp, stop, ss+1, stopst, lev-1));
+			return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
 		else
 			return(dp);
 		break;
@@ -716,7 +720,7 @@ sopno lev;			/* PLUS nesting level */
 		esub = ss + OPND(s) - 1;
 		assert(OP(m->g->strip[esub]) == OOR1);
 		for (;;) {	/* find first matching branch */
-			dp = backref(m, sp, stop, ssub, esub, lev);
+			dp = backref(m, sp, stop, ssub, esub, lev, rec);
 			if (dp != NULL)
 				return(dp);
 			/* that one missed, try next one */
@@ -737,7 +741,7 @@ sopno lev;			/* PLUS nesting level */
 		assert(0 < i && i <= m->g->nsub);
 		offsave = m->pmatch[i].rm_so;
 		m->pmatch[i].rm_so = sp - m->offp;
-		dp = backref(m, sp, stop, ss+1, stopst, lev);
+		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 		if (dp != NULL)
 			return(dp);
 		m->pmatch[i].rm_so = offsave;
@@ -748,7 +752,7 @@ sopno lev;			/* PLUS nesting level */
 		assert(0 < i && i <= m->g->nsub);
 		offsave = m->pmatch[i].rm_eo;
 		m->pmatch[i].rm_eo = sp - m->offp;
-		dp = backref(m, sp, stop, ss+1, stopst, lev);
+		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 		if (dp != NULL)
 			return(dp);
 		m->pmatch[i].rm_eo = offsave;
diff --git a/lib/libc/regex/grot/tests b/lib/libc/regex/grot/tests
index 07e9dfb8539d3..95a21bb0fdd4b 100644
--- a/lib/libc/regex/grot/tests
+++ b/lib/libc/regex/grot/tests
@@ -165,6 +165,30 @@ a\(\(b\)*\2\)*d		b	abbbd	abbbd
 \(a\)\1bc*d	b	aabcccd	aabcccd
 \(a\)\1bc*[ce]d	b	aabcccd	aabcccd
 ^\(a\)\1b\(c\)*cd$	b	aabcccd	aabcccd
+\(b*\)\(a*\1\)*	b	ab	a
+\([^_]*\)\(_*\1\)*	b	foo_foo_bar_bar_bar_baz	foo_foo	foo,_foo
+\([^_]*\)\(_*\1\)*	b	bar_bar_bar_baz	bar_bar_bar	bar,_bar
+\([^_]*\)\(_*\1\)*	b	foo_bar_baz	foo	foo
+\(.*\)\1	b	""	""
+\(.*\)\1	b	a	""
+\(.*\)\1	b	aa	aa
+\(.*\)\1	b	aaa	aa
+\(.*\)\1	b	aaaa	aaaa
+\([^_]*\)\1	b	""	""
+\([^_]*\)\1	b	a	""
+\([^_]*\)\1	b	aa	aa
+\([^_]*\)\1	b	aaa	aa
+\([^_]*\)\1	b	aaaa	aaaa
+foo\(.*\)bar\1	b	foolbarl	foolbarl	l
+foo\(.*\)bar\1	b	foobar	foobar	""
+\(\(.\)b\)*\1	b	aba
+\(\(.\)b\)*\1	b	abba
+\(\(.\)b\)*\1	b	abbba
+\(\(.\)b\)*\1	b	abbbba	bbbb	bb,b
+\(\(.\)b\)*\1	b	abbbbba	abbbbb	bb,b
+\(\(.\)b\)*\1	b	abbbbbba	abbbbb	bb,b
+\(\(.\)b\)*\1	b	abbbbbbbbbbbbbba	abbbbbbbbbbbbb	bb,b
+\(\(.\)b\)*\1	b	abbbbbbbbbbbbbbba	abbbbbbbbbbbbbbb	bb,b
 
 # ordinary repetitions
 ab*c		&	abc	abc