Make the m4 machine stack dynamically sized.

Fix strspace automatic extension.
The assumption that simply updating the current pointer works is false,
there are cases where previous entries on the stack would absorp vast
amounts of string space, and overload the non-updated entries.

To fix it, we use a shadow copy of the stack, which only records which
entries are pointers within strspace, so that a resize can adjust all
those pointers at once.

Reviewed by millert@

4 files changed, 68 insertions, 45 deletions

diff --git a/usr.bin/m4/extern.h b/usr.bin/m4/extern.h
index a94f75abe49..4c2897d935c 100644
--- a/usr.bin/m4/extern.h
+++ b/usr.bin/m4/extern.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: extern.h,v 1.18 2000/03/18 01:06:55 espie Exp $	*/
+/*	$OpenBSD: extern.h,v 1.19 2000/07/02 01:17:00 espie Exp $	*/
 /*	$NetBSD: extern.h,v 1.3 1996/01/13 23:25:24 pk Exp $	*/
 
 /*-
@@ -91,7 +91,8 @@ extern void	release_input __P((struct input_file *));
 
 
 extern ndptr hashtab[];		/* hash table for macros etc. */
-extern stae mstack[];		/* stack of m4 machine */
+extern stae *mstack;		/* stack of m4 machine */
+extern char *sstack;		/* shadow stack, for string space extension */
 extern FILE *active;		/* active output file pointer */
 extern struct input_file infile[];/* input file stack (0=stdin) */
 extern FILE *outfile[];		/* diversion array(0=bitbucket) */
diff --git a/usr.bin/m4/main.c b/usr.bin/m4/main.c
index cd1c0ebdc5a..33a1c673644 100644
--- a/usr.bin/m4/main.c
+++ b/usr.bin/m4/main.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: main.c,v 1.33 2000/07/02 01:13:07 espie Exp $	*/
+/*	$OpenBSD: main.c,v 1.34 2000/07/02 01:17:00 espie Exp $	*/
 /*	$NetBSD: main.c,v 1.12 1997/02/08 23:54:49 cgd Exp $	*/
 
 /*-
@@ -47,7 +47,7 @@ static char copyright[] =
 #if 0
 static char sccsid[] = "@(#)main.c	8.1 (Berkeley) 6/6/93";
 #else
-static char rcsid[] = "$OpenBSD: main.c,v 1.33 2000/07/02 01:13:07 espie Exp $";
+static char rcsid[] = "$OpenBSD: main.c,v 1.34 2000/07/02 01:17:00 espie Exp $";
 #endif
 #endif /* not lint */
 
@@ -66,6 +66,7 @@ static char rcsid[] = "$OpenBSD: main.c,v 1.33 2000/07/02 01:13:07 espie Exp $";
 #include <ctype.h>
 #include <string.h>
 #include <stddef.h>
+#include <stdlib.h>
 #include <err.h>
 #include "mdef.h"
 #include "stdd.h"
@@ -73,7 +74,9 @@ static char rcsid[] = "$OpenBSD: main.c,v 1.33 2000/07/02 01:13:07 espie Exp $";
 #include "pathnames.h"
 
 ndptr hashtab[HASHSIZE];	/* hash table for macros etc.  */
-stae mstack[STACKMAX+1]; 	/* stack of m4 machine         */
+stae *mstack;		 	/* stack of m4 machine         */
+char *sstack;		 	/* shadow stack, for string space extension */
+static size_t STACKMAX;		/* current maximum size of stack */
 int sp; 			/* current m4  stack pointer   */
 int fp; 			/* m4 call frame pointer       */
 struct input_file infile[MAXINP];/* input file stack (0=stdin)  */
@@ -160,6 +163,8 @@ static void initkwds __P((void));
 static ndptr inspect __P((char, char *));
 static int do_look_ahead __P((int, const char *));
 
+static void enlarge_stack __P((void));
+
 int main __P((int, char *[]));
 
 int
@@ -177,6 +182,10 @@ main(argc,argv)
 
 	initkwds();
 	initspaces();
+	STACKMAX = INITSTACKMAX;
+
+	mstack = (stae *)xalloc(sizeof(stae) * STACKMAX);
+	sstack = (char *)xalloc(STACKMAX);
 
 	while ((c = getopt(argc, argv, "gtD:U:o:I:")) != -1)
 		switch(c) {
@@ -283,7 +292,7 @@ do_look_ahead(t, token)
 static void
 macro()
 {
-	char token[MAXTOK];
+	char token[MAXTOK+1];
 	int t, l;
 	ndptr p;
 	int  nlpar;
@@ -308,9 +317,9 @@ macro()
 		/*
 		 * now push the string arguments:
 		 */
-				pushs(p->defn);	      /* defn string */
-				pushs(p->name);	      /* macro name  */
-				pushs(ep);	      /* start next..*/
+				pushs1(p->defn);	/* defn string */
+				pushs1(p->name);	/* macro name  */
+				pushs(ep);	      	/* start next..*/
 
 				if (l != LPAREN)  {   /* add bracks  */
 					putback(RPAREN);
@@ -578,3 +587,16 @@ dump_stack(t, lev)
 			t[i].name, t[i].line);
 	}
 }
+
+
+static void 
+enlarge_stack()
+{
+	STACKMAX *= 2;
+	fprintf(stderr, "%u\n", STACKMAX);
+	mstack = realloc(mstack, sizeof(stae) * STACKMAX);
+	sstack = realloc(sstack, STACKMAX);
+	if (mstack == NULL || sstack == NULL)
+		errx(1, "Evaluation stack overflow (%lu)", 
+		    (unsigned long)STACKMAX);
+}
diff --git a/usr.bin/m4/mdef.h b/usr.bin/m4/mdef.h
index 8d7278db3b2..c7201e91d38 100644
--- a/usr.bin/m4/mdef.h
+++ b/usr.bin/m4/mdef.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: mdef.h,v 1.14 2000/03/11 15:54:44 espie Exp $	*/
+/*	$OpenBSD: mdef.h,v 1.15 2000/07/02 01:17:00 espie Exp $	*/
 /*	$NetBSD: mdef.h,v 1.7 1996/01/13 23:25:27 pk Exp $	*/
 
 /*
@@ -112,8 +112,8 @@
 #define MAXOUT          10              /* maximum # of diversions 	    */
 #define MAXSTR          512             /* maximum size of string  	    */
 #define BUFSIZE         4096            /* starting size of pushback buffer */
-#define STACKMAX        4096            /* size of call stack      	    */
-#define STRSPMAX        4096            /* starting size of string space    */
+#define INITSTACKMAX    4096           	/* starting size of call stack      */
+#define STRSPMAX        64             /* starting size of string space    */
 #define MAXTOK          MAXSTR          /* maximum chars in a tokn 	    */
 #define HASHSIZE        199             /* maximum size of hashtab 	    */
 #define MAXCCHARS	5		/* max size of comment/quote delim  */
@@ -168,8 +168,29 @@ struct input_file {
  *      pushs() - push a string pointer onto stack
  */
 #define gpbc() 	 (bp > bufbase) ? *--bp : obtain_char(infile+ilevel)
-#define pushf(x) if (sp < STACKMAX) mstack[++sp].sfra = (x)
-#define pushs(x) if (sp < STACKMAX) mstack[++sp].sstr = (x)
+#define pushf(x) 			\
+	do {				\
+		if (++sp == STACKMAX) 	\
+			enlarge_stack();\
+		mstack[sp].sfra = (x);	\
+		sstack[sp] = 0; \
+	} while (0);
+
+#define pushs(x) 			\
+	do {				\
+		if (++sp == STACKMAX) 	\
+			enlarge_stack();\
+		mstack[sp].sstr = (x);	\
+		sstack[sp] = 1; \
+	} while (0);
+
+#define pushs1(x) 			\
+	do {				\
+		if (++sp == STACKMAX) 	\
+			enlarge_stack();\
+		mstack[sp].sstr = (x);	\
+		sstack[sp] = 0; \
+	} while (0);
 
 /*
  *	    .				   .
@@ -196,6 +217,6 @@ struct input_file {
  */
 #define PARLEV  (mstack[fp].sfra)
 #define CALTYP  (mstack[fp-1].sfra)
-#define PREVEP	compute_prevep() 
+#define PREVEP	(mstack[fp+3].sstr)
 #define PREVSP	(fp-3)
 #define PREVFP	(mstack[fp-2].sfra)
diff --git a/usr.bin/m4/misc.c b/usr.bin/m4/misc.c
index 8858bad5e4c..bbe95b31f9c 100644
--- a/usr.bin/m4/misc.c
+++ b/usr.bin/m4/misc.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: misc.c,v 1.18 2000/03/11 15:54:44 espie Exp $	*/
+/*	$OpenBSD: misc.c,v 1.19 2000/07/02 01:17:00 espie Exp $	*/
 /*	$NetBSD: misc.c,v 1.6 1995/09/28 05:37:41 tls Exp $	*/
 
 /*
@@ -41,7 +41,7 @@
 #if 0
 static char sccsid[] = "@(#)misc.c	8.1 (Berkeley) 6/6/93";
 #else
-static char rcsid[] = "$OpenBSD: misc.c,v 1.18 2000/03/11 15:54:44 espie Exp $";
+static char rcsid[] = "$OpenBSD: misc.c,v 1.19 2000/07/02 01:17:00 espie Exp $";
 #endif
 #endif /* not lint */
 
@@ -64,7 +64,6 @@ static char *strspace;	/* string space for evaluation */
 static char *endest;	/* end of string space	       */
 static size_t strsize = STRSPMAX;
 static size_t bufsize = BUFSIZE;
-static int low_sp = 0;
 
 char *buf;			/* push-back buffer	       */
 char *bufbase;			/* the base for current ilevel */
@@ -171,32 +170,28 @@ initspaces()
 		bbase[i] = buf;
 }
 
-/* XXX when chrsave is called, the current argument is
- * always topmost on the stack.  We make use of this to
- * duplicate it transparently, and to reclaim the correct
- * space when the stack is unwound.
- */
 static void 
 enlarge_strspace()
 {
 	char *newstrspace;
+	int i;
 
-	low_sp = sp;
 	strsize *= 2;
 	newstrspace = malloc(strsize + 1);
 	if (!newstrspace)
 		errx(1, "string space overflow");
 	memcpy(newstrspace, strspace, strsize/2);
-		/* reclaim memory in the easy, common case. */
-	if (ep == strspace)
-		free(strspace);
-	mstack[sp].sstr = (mstack[sp].sstr-strspace) + newstrspace;
+	for (i = 0; i <= sp; i++) 
+		if (sstack[i])
+			mstack[i].sstr = (mstack[i].sstr - strspace) 
+			    + newstrspace;
 	ep = (ep-strspace) + newstrspace;
+	free(strspace);
 	strspace = newstrspace;
 	endest = strspace + strsize;
 }
 
-static void 
+static void
 enlarge_bufspace()
 {
 	char *newbuf;
@@ -226,22 +221,6 @@ chrsave(c)
 	*ep++ = c;
 }
 
-/* 
- * so we reclaim what string space we can
- */
-char * 
-compute_prevep()
-{
-	if (fp+3 <= low_sp)
-		{
-		return strspace;
-		}
-	else
-		{
-		return mstack[fp+3].sstr;
-		}
-}
-
 /*
  * read in a diversion file, and dispose it.
  */