memory waste in macro recursion

[Eric Blake]

I discovered a quasi-memory leak during my efforts on $@ references.  It is not 
a true memory leak, because the memory lived on an obstack, and was eventually 
freed once recursion ends; however, it was rather wasteful of resources to keep 
that much memory live when it will never be referenced again.  Patching the 
leak gave such impressive results, with so little code, that I'm installing 
this patch now on the branch, and a similar one on the head.  It dramatically 
cuts the peak memory usage of examples/loop.m4, with negligible impact to 
speed, thereby allowing much higher iteration limits before running into 
machine limits.  Tested with 'm4 -Iexamples -Dlimit=n loop.m4':

            n=1000          n=1500          n=2000
pre-patch:  17.8Mb 1.575s   40.7Mb 3.732s   73.0Mb 6.763s
post-patch:  2.0Mb 1.607s    2.0Mb 3.732s    2.0Mb 6.747s

For this particular patch, loop.m4 still exhibits quadratic timing growth, but 
the memory usage dropped from O(n^2) to O(1)!

Progress on my $@ patch series: I've finally resolved my memory allocation 
issues (I spent the better part of my last two weeks of hacking time figuring 
out how to correctly lengthen the lifetime of references without hanging on to 
memory too long).  I have also gotten foreachq3.m4 reduced from quadratic down 
to logarithmic scaling in time; but am still trying to get similar results for 
foreachq2.m4 (as well as see if I can get closer to linear instead of log 
scaling).  Would anyone be interested if I pushed my progress onto a public git 
branch?

From: Eric Blake <address@hidden>
Date: Tue, 13 Nov 2007 11:59:43 -0700
Subject: [PATCH] Fix memory leak in tail recursion.

* src/input.c (push_string_init): Let go of memory earlier.
(next_char_1): Make end of string detection reliable.
(match_input): Simplify use of push_string_init.
* NEWS: Document this fix.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog   |    8 ++++++++
 NEWS        |    1 +
 src/input.c |   53 +++++++++++++++++++++++++++++++++++++++++------------
 3 files changed, 50 insertions(+), 12 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 86d8ad4..b52f3e0 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2007-11-13  Eric Blake  <address@hidden>
+
+       Fix memory leak in tail recursion.
+       * src/input.c (push_string_init): Let go of memory earlier.
+       (next_char_1): Make end of string detection reliable.
+       (match_input): Simplify use of push_string_init.
+       * NEWS: Document this fix.
+
 2007-11-07  Eric Blake  <address@hidden>
 
        * doc/m4.texinfo (Pseudo Arguments): Test more corner cases.
diff --git a/NEWS b/NEWS
index 6d667f0..b92630b 100644
--- a/NEWS
+++ b/NEWS
@@ -14,6 +14,7 @@ Version 1.4.11 - ?? ??? 2007, by ????  (git version 1.4.10a-*)
   possible to concatenate a builtin macro with anything else.
 * Several improvements in `index', `regexp', and `patsubst' builtins to
   speed up typical Autoconf usage.
+* Memory usage is greatly reduced in recursive macros.
 * A number of portability improvements inherited from gnulib.
 
 Version 1.4.10 - 09 Jul 2007, by Eric Blake  (CVS version 1.4.9c)
diff --git a/src/input.c b/src/input.c
index 23903f3..3ef7b83 100644
--- a/src/input.c
+++ b/src/input.c
@@ -241,7 +241,37 @@ push_macro (builtin_func *func)
 struct obstack *
 push_string_init (void)
 {
+  /* Free any memory occupied by completely parsed strings.  */
+  bool pruning = true;
   assert (next == NULL);
+  while (isp && pruning)
+    {
+      switch (isp->type)
+       {
+       case INPUT_STRING:
+         if (*isp->u.u_s.string)
+           pruning = false;
+         break;
+
+       case INPUT_FILE:
+       case INPUT_MACRO:
+         pruning = false;
+         break;
+
+       default:
+         assert (!"push_string_init");
+         abort ();
+       }
+      if (pruning)
+       {
+         next = isp;
+         isp = isp->prev;
+       }
+    }
+  if (next)
+    obstack_free (current_input, next);
+
+  /* Reserve the next location on the obstack.  */
   next = (input_block *) obstack_alloc (current_input,
                                        sizeof (struct input_block));
   next->type = INPUT_STRING;
@@ -497,9 +527,12 @@ next_char_1 (void)
       switch (isp->type)
        {
        case INPUT_STRING:
-         ch = to_uchar (*isp->u.u_s.string++);
+         ch = to_uchar (*isp->u.u_s.string);
          if (ch != '\0')
-           return ch;
+           {
+             *isp->u.u_s.string++;
+             return ch;
+           }
          break;
 
        case INPUT_FILE:
@@ -536,10 +569,10 @@ next_char_1 (void)
     }
 }
 
-/*------------------------------------------------------------------------.
-| skip_line () simply discards all immediately following characters, upto |
-| the first newline.  It is only used from m4_dnl ().                    |
-`------------------------------------------------------------------------*/
+/*-------------------------------------------------------------------.
+| skip_line () simply discards all immediately following characters, |
+| up to the first newline.  It is only used from m4_dnl ().          |
+`-------------------------------------------------------------------*/
 
 void
 skip_line (void)
@@ -607,12 +640,8 @@ match_input (const char *s, bool consume)
     }
 
   /* Failed or shouldn't consume, push back input.  */
-  {
-    struct obstack *h = push_string_init ();
-
-    /* `obstack_grow' may be macro evaluating its arg 1 several times. */
-    obstack_grow (h, t, n);
-  }
+  push_string_init ();
+  obstack_grow (current_input, t, n);
   push_string_finish ();
   return result;
 }
-- 
1.5.3.2