awk: remove custom pool allocator for temporary awk variables

It seems to be designed to reduce overhead of malloc's auxiliary data,
by allocating at least 64 variables as a block.
With "struct var" being about 20-32 bytes long (32/64 bits),
malloc overhead for one temporary indeed is high, ~33% more memory used
than needed.

function                                             old     new   delta
evaluate                                            3137    3145      +8
modprobe_main                                        798     803      +5
exec_builtin                                        1414    1419      +5
awk_printf                                           476     481      +5
as_regex                                             132     137      +5
EMSG_INTERNAL_ERROR                                   15       -     -15
nvfree                                               169     116     -53
nvalloc                                              145       -    -145
------------------------------------------------------------------------------
(add/remove: 0/2 grow/shrink: 5/1 up/down: 28/-213)          Total: -185 bytes

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>

1 files changed, 61 insertions, 103 deletions

diff --git a/editors/awk.c b/editors/awk.c
index a4cd3cf93..35c11ec58 100644
--- a/editors/awk.c
+++ b/editors/awk.c
@@ -93,7 +93,6 @@ enum {
 };
 
 #define MAXVARFMT       240
-#define MINNVBLOCK      64
 
 /* variable flags */
 #define VF_NUMBER       0x0001  /* 1 = primary type is number */
@@ -120,8 +119,8 @@ typedef struct walker_list {
 /* Variable */
 typedef struct var_s {
         unsigned type;            /* flags */
-        double number;
         char *string;
+        double number;
         union {
                 int aidx;               /* func arg idx (for compilation stage) */
                 struct xhash_s *array;  /* array ptr */
@@ -192,15 +191,6 @@ typedef struct node_s {
         } a;
 } node;
 
-/* Block of temporary variables */
-typedef struct nvblock_s {
-        int size;
-        var *pos;
-        struct nvblock_s *prev;
-        struct nvblock_s *next;
-        var nv[];
-} nvblock;
-
 typedef struct tsplitter_s {
         node n;
         regex_t re[2];
@@ -537,7 +527,6 @@ struct globals {
         int nfields;
         int maxfields; /* used in fsrealloc() only */
         var *Fields;
-        nvblock *g_cb;
         char *g_pos;
         char g_saved_ch;
         smallint icase;
@@ -605,7 +594,6 @@ struct globals2 {
 #define nfields      (G1.nfields     )
 #define maxfields    (G1.maxfields   )
 #define Fields       (G1.Fields      )
-#define g_cb         (G1.g_cb        )
 #define g_pos        (G1.g_pos       )
 #define g_saved_ch   (G1.g_saved_ch  )
 #define icase        (G1.icase       )
@@ -640,7 +628,6 @@ static int awk_exit(int) NORETURN;
 
 /* ---- error handling ---- */
 
-static const char EMSG_INTERNAL_ERROR[] ALIGN1 = "Internal error";
 static const char EMSG_UNEXP_EOS[] ALIGN1 = "Unexpected end of string";
 static const char EMSG_UNEXP_TOKEN[] ALIGN1 = "Unexpected token";
 static const char EMSG_DIV_BY_ZERO[] ALIGN1 = "Division by zero";
@@ -1050,77 +1037,6 @@ static int istrue(var *v)
         return (v->string && v->string[0]);
 }
 
-/* temporary variables allocator. Last allocated should be first freed */
-static var *nvalloc(int n)
-{
-        nvblock *pb = NULL;
-        var *v, *r;
-        int size;
-
-        while (g_cb) {
-                pb = g_cb;
-                if ((g_cb->pos - g_cb->nv) + n <= g_cb->size)
-                        break;
-                g_cb = g_cb->next;
-        }
-
-        if (!g_cb) {
-                size = (n <= MINNVBLOCK) ? MINNVBLOCK : n;
-                g_cb = xzalloc(sizeof(nvblock) + size * sizeof(var));
-                g_cb->size = size;
-                g_cb->pos = g_cb->nv;
-                g_cb->prev = pb;
-                /*g_cb->next = NULL; - xzalloc did it */
-                if (pb)
-                        pb->next = g_cb;
-        }
-
-        v = r = g_cb->pos;
-        g_cb->pos += n;
-
-        while (v < g_cb->pos) {
-                v->type = 0;
-                v->string = NULL;
-                v++;
-        }
-
-        return r;
-}
-
-static void nvfree(var *v)
-{
-        var *p;
-
-        if (v < g_cb->nv || v >= g_cb->pos)
-                syntax_error(EMSG_INTERNAL_ERROR);
-
-        for (p = v; p < g_cb->pos; p++) {
-                if ((p->type & (VF_ARRAY | VF_CHILD)) == VF_ARRAY) {
-                        clear_array(iamarray(p));
-                        free(p->x.array->items);
-                        free(p->x.array);
-                }
-                if (p->type & VF_WALK) {
-                        walker_list *n;
-                        walker_list *w = p->x.walker;
-                        debug_printf_walker("nvfree: freeing walker @%p\n", &p->x.walker);
-                        p->x.walker = NULL;
-                        while (w) {
-                                n = w->prev;
-                                debug_printf_walker(" free(%p)\n", w);
-                                free(w);
-                                w = n;
-                        }
-                }
-                clrvar(p);
-        }
-
-        g_cb->pos = v;
-        while (g_cb->prev && g_cb->pos == g_cb->nv) {
-                g_cb = g_cb->prev;
-        }
-}
-
 /* ------- awk program text parsing ------- */
 
 /* Parse next token pointed by global pos, place results into global t_XYZ variables.
@@ -1793,6 +1709,41 @@ static void parse_program(char *p)
 
 /* -------- program execution part -------- */
 
+/* temporary variables allocator */
+static var *nvalloc(int sz)
+{
+        return xzalloc(sz * sizeof(var));
+}
+
+static void nvfree(var *v, int sz)
+{
+        var *p = v;
+
+        while (--sz >= 0) {
+                if ((p->type & (VF_ARRAY | VF_CHILD)) == VF_ARRAY) {
+                        clear_array(iamarray(p));
+                        free(p->x.array->items);
+                        free(p->x.array);
+                }
+                if (p->type & VF_WALK) {
+                        walker_list *n;
+                        walker_list *w = p->x.walker;
+                        debug_printf_walker("nvfree: freeing walker @%p\n", &p->x.walker);
+                        p->x.walker = NULL;
+                        while (w) {
+                                n = w->prev;
+                                debug_printf_walker(" free(%p)\n", w);
+                                free(w);
+                                w = n;
+                        }
+                }
+                clrvar(p);
+                p++;
+        }
+
+        free(v);
+}
+
 static node *mk_splitter(const char *s, tsplitter *spl)
 {
         regex_t *re, *ire;
@@ -1814,9 +1765,9 @@ static node *mk_splitter(const char *s, tsplitter *spl)
         return n;
 }
 
-/* use node as a regular expression. Supplied with node ptr and regex_t
+/* Use node as a regular expression. Supplied with node ptr and regex_t
  * storage space. Return ptr to regex (if result points to preg, it should
- * be later regfree'd manually
+ * be later regfree'd manually).
  */
 static regex_t *as_regex(node *op, regex_t *preg)
 {
@@ -1840,7 +1791,7 @@ static regex_t *as_regex(node *op, regex_t *preg)
                 cflags &= ~REG_EXTENDED;
                 xregcomp(preg, s, cflags);
         }
-        nvfree(v);
+        nvfree(v, 1);
         return preg;
 }
 
@@ -2292,6 +2243,8 @@ static char *awk_printf(node *n, int *len)
         var *v, *arg;
 
         v = nvalloc(1);
+//TODO: above, to avoid allocating a single temporary var, take a pointer
+//to a temporary that our caller (evaluate()) already has?
         fmt = f = xstrdup(getvar_s(evaluate(nextarg(&n), v)));
 
         i = 0;
@@ -2333,7 +2286,7 @@ static char *awk_printf(node *n, int *len)
         }
 
         free(fmt);
-        nvfree(v);
+        nvfree(v, 1);
         b = xrealloc(b, i + 1);
         b[i] = '\0';
 #if ENABLE_FEATURE_AWK_GNU_EXTENSIONS
@@ -2661,14 +2614,14 @@ static NOINLINE var *exec_builtin(node *op, var *res)
                 break;
         }
 
-        nvfree(tv);
+        nvfree(tv, 4);
         return res;
 #undef tspl
 }
 
 /*
  * Evaluate node - the heart of the program. Supplied with subtree
- * and place where to store result. returns ptr to result.
+ * and place where to store result. Returns ptr to result.
  */
 #define XC(n) ((n) >> 8)
 
@@ -2953,33 +2906,38 @@ static var *evaluate(node *op, var *res)
                         break;
 
                 case XC( OC_FUNC ): {
-                        var *vbeg, *v;
+                        var *tv, *sv_fnargs;
                         const char *sv_progname;
+                        int nargs1, i;
+
                         debug_printf_eval("FUNC\n");
 
-                        /* The body might be empty, still has to eval the args */
                         if (!op->r.n->info && !op->r.f->body.first)
                                 syntax_error(EMSG_UNDEF_FUNC);
 
-                        vbeg = v = nvalloc(op->r.f->nargs + 1);
+                        /* The body might be empty, still has to eval the args */
+                        nargs1 = op->r.f->nargs + 1;
+                        tv = nvalloc(nargs1);
+                        i = 0;
                         while (op1) {
+//TODO: explain why one iteration is done even for the case p->r.f->nargs == 0
                                 var *arg = evaluate(nextarg(&op1), v1);
-                                copyvar(v, arg);
-                                v->type |= VF_CHILD;
-                                v->x.parent = arg;
-                                if (++v - vbeg >= op->r.f->nargs)
+                                copyvar(&tv[i], arg);
+                                tv[i].type |= VF_CHILD;
+                                tv[i].x.parent = arg;
+                                if (++i >= op->r.f->nargs)
                                         break;
                         }
 
-                        v = fnargs;
-                        fnargs = vbeg;
+                        sv_fnargs = fnargs;
                         sv_progname = g_progname;
 
+                        fnargs = tv;
                         res = evaluate(op->r.f->body.first, res);
+                        nvfree(fnargs, nargs1);
 
                         g_progname = sv_progname;
-                        nvfree(fnargs);
-                        fnargs = v;
+                        fnargs = sv_fnargs;
 
                         break;
                 }
@@ -3301,7 +3259,7 @@ static var *evaluate(node *op, var *res)
                         break;
         } /* while (op) */
 
-        nvfree(v1);
+        nvfree(v1, 2);
         debug_printf_eval("returning from %s(): %p\n", __func__, res);
         return res;
 #undef fnargs