Merge branch 'master' into feature/api-mpfr

10 files changed, 171 insertions, 72 deletions

diff --git a/ChangeLog b/ChangeLog
index a785ed5c..7eadd5fb 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -5,9 +5,20 @@
 
 2017-04-10         Andrew J. Schorr     <aschorr@telemetry-investments.com>
 
+	* awk.h (enum opcodeval): For the avoidance of doubt, specify that
+	Op_illegal must equal zero.
+	* symbol.c (bcfree): Improve clarity by setting opcode to Op_illegal
+	instead of 0.
+	(free_bc_mempool): Improve clarity by comparing opcode to Op_illegal
+	instead of to 0.
+
 	* field.c (set_FIELDWIDTHS): Set use_chars to awk_true, since its
 	type is awk_bool_t.
 
+2017-04-10         Arnold D. Robbins     <arnold@skeeve.com>
+
+	* symbol.c (free_bc_mempool): Change `first' from int to bool.
+
 2017-04-09         Andrew J. Schorr     <aschorr@telemetry-investments.com>
 
 	* field.c (fw_parse_field): Edit comment about resetting shift state.
@@ -21,6 +32,36 @@
 
 	* awk.h (die_via_sigpipe) [__MINGW32__]: MinGW-specific definition.
 
+2017-04-07         Andrew J. Schorr     <aschorr@telemetry-investments.com>
+
+	* awk.h (INSTRUCTION_POOL): Redefine as an array of structures so we
+	can track allocated blocks.
+	* symbol.c (pools): Make it a pointer to avoid copying.
+	(struct instruction_block): Define structure to hold a block of
+	allocated instructions.
+	(bcfree): Update to use new INSTRUCTION_POOL definition.
+	(bcalloc): Allocate an instruction by searching first on the free
+	list, second for free space in the current block, or third by
+	allocating a new block.
+	(set_context): Update to reflect that pools is now a pointer.
+	(free_bc_mempool): New helper function to free a pool of a certain size.
+	(fre_bcpool): Call free_bc_mempool for each pool.
+
+2017-04-04         Arnold D. Robbins     <arnold@skeeve.com>
+
+	* awk.h (INSTRUCTION): Add pool_size member.
+	[MAX_INSTRUCTION_ALLOC]: New macro.
+	(INSTRUCTION_POOL): New type.
+	(struct context): Use INSTRUCTION_POOL.
+	* array.c (assoc_list): Reorg the code a bit to make sure
+	to alway free the INSTRUCTIONs allocated for calling a
+	user-supplied sorting function. Based on code by
+	Andrew Schorr.
+	* symbol.c (free_bcpool): Rework to use an INSTRUCTION_POOL.
+	(bcfree, bcalloc): Rework to use separate chains in
+	the instruction pool.
+	(set_context): Update appropriately.
+
 2017-03-27         Arnold D. Robbins     <arnold@skeeve.com>
 
 	* field.c (parse_field_func_t): New typedef. Used as needed.
diff --git a/array.c b/array.c
index cee1c729..3159bfdc 100644
--- a/array.c
+++ b/array.c
@@ -1353,12 +1353,22 @@ assoc_list(NODE *symbol, const char *sort_str, sort_context_t sort_ctxt)
 	list = symbol->alist(symbol, & akind);
 	assoc_kind = (assoc_kind_t) akind.flags;	/* symbol->alist can modify it */
 
-	if (list == NULL || ! cmp_func || (assoc_kind & (AASC|ADESC)) != 0)
-		return list;	/* empty list or unsorted, or list already sorted */
+	/* check for empty list or unsorted, or list already sorted */
+	if (list != NULL && cmp_func != NULL && (assoc_kind & (AASC|ADESC)) == 0) {
+		num_elems = assoc_length(symbol);
 
-	num_elems = assoc_length(symbol);
+		qsort(list, num_elems, elem_size * sizeof(NODE *), cmp_func); /* shazzam! */
 
-	qsort(list, num_elems, elem_size * sizeof(NODE *), cmp_func); /* shazzam! */
+		if (sort_ctxt == SORTED_IN && (assoc_kind & (AINDEX|AVALUE)) == (AINDEX|AVALUE)) {
+			/* relocate all index nodes to the first half of the list. */
+			for (j = 1; j < num_elems; j++)
+				list[j] = list[2 * j];
+
+			/* give back extra memory */
+
+			erealloc(list, NODE **, num_elems * sizeof(NODE *), "assoc_list");
+		}
+	}
 
 	if (cmp_func == sort_user_func) {
 		code = POP_CODE();
@@ -1367,15 +1377,5 @@ assoc_list(NODE *symbol, const char *sort_str, sort_context_t sort_ctxt)
 		bcfree(code);                   /* Op_func_call */
 	}
 
-	if (sort_ctxt == SORTED_IN && (assoc_kind & (AINDEX|AVALUE)) == (AINDEX|AVALUE)) {
-		/* relocate all index nodes to the first half of the list. */
-		for (j = 1; j < num_elems; j++)
-			list[j] = list[2 * j];
-
-		/* give back extra memory */
-
-		erealloc(list, NODE **, num_elems * sizeof(NODE *), "assoc_list");
-	}
-
 	return list;
 }
diff --git a/awk.h b/awk.h
index 69f6ae65..084e7dda 100644
--- a/awk.h
+++ b/awk.h
@@ -597,8 +597,7 @@ typedef enum lintvals {
 /* --------------------------------Instruction ---------------------------------- */
 
 typedef enum opcodeval {
-	/* illegal entry == 0 */
-	Op_illegal,
+	Op_illegal = 0,		/* illegal entry */
 
 	/* binary operators */
 	Op_times,
@@ -783,6 +782,7 @@ typedef struct exp_instruction {
 	} x;
 
 	short source_line;
+	short pool_size;	// memory management in symbol.c
 	OPCODE opcode;
 } INSTRUCTION;
 
@@ -1031,9 +1031,19 @@ typedef struct srcfile {
 	int lasttok;
 } SRCFILE;
 
+// structure for INSTRUCTION pool, needed mainly for debugger
+typedef struct instruction_pool {
+#define MAX_INSTRUCTION_ALLOC	3	// we don't call bcalloc with more than this
+	struct instruction_mem_pool {
+		struct instruction_block *block_list;
+		INSTRUCTION *free_space;	// free location in active block
+		INSTRUCTION *free_list;
+	} pool[MAX_INSTRUCTION_ALLOC];
+} INSTRUCTION_POOL;
+
 /* structure for execution context */
 typedef struct context {
-	INSTRUCTION pools;
+	INSTRUCTION_POOL pools;
 	NODE symbols;
 	INSTRUCTION rule_list;
 	SRCFILE srcfiles;
diff --git a/symbol.c b/symbol.c
index 65ed4d90..ea5ee0af 100644
--- a/symbol.c
+++ b/symbol.c
@@ -37,7 +37,7 @@ static NODE *symbol_list;
 static void (*install_func)(NODE *) = NULL;
 static NODE *make_symbol(const char *name, NODETYPE type);
 static NODE *install(const char *name, NODE *parm, NODETYPE type);
-static void free_bcpool(INSTRUCTION *pl);
+static void free_bcpool(INSTRUCTION_POOL *pl);
 
 static AWK_CONTEXT *curr_ctxt = NULL;
 static int ctxt_level;
@@ -693,21 +693,30 @@ check_param_names(void)
 	return result;
 }
 
-#define pool_size	d.dl
-#define freei		x.xi
-static INSTRUCTION *pool_list;
+static INSTRUCTION_POOL *pools;
 
-/* INSTR_CHUNK must be > largest code size (3) */
-#define INSTR_CHUNK 127
+/*
+ * For best performance, the INSTR_CHUNK value should be divisible by all
+ * possible sizes, i.e. 1 through MAX_INSTRUCTION_ALLOC. Otherwise, there
+ * will be wasted space at the end of the block.
+ */
+#define INSTR_CHUNK (2*3*21)
+
+struct instruction_block {
+	struct instruction_block *next;
+	INSTRUCTION i[INSTR_CHUNK];
+};
 
 /* bcfree --- deallocate instruction */
 
 void
 bcfree(INSTRUCTION *cp)
 {
-	cp->opcode = 0;
-	cp->nexti = pool_list->freei;
-	pool_list->freei = cp;
+	assert(cp->pool_size >= 1 && cp->pool_size <= MAX_INSTRUCTION_ALLOC);
+
+	cp->opcode = Op_illegal;
+	cp->nexti = pools->pool[cp->pool_size - 1].free_list;
+	pools->pool[cp->pool_size - 1].free_list = cp;
 }
 
 /* bcalloc --- allocate a new instruction */
@@ -716,38 +725,28 @@ INSTRUCTION *
 bcalloc(OPCODE op, int size, int srcline)
 {
 	INSTRUCTION *cp;
+	struct instruction_mem_pool *pool;
+
+	assert(size >= 1 && size <= MAX_INSTRUCTION_ALLOC);
+	pool = &pools->pool[size - 1];
 
-	if (size > 1) {
-		/* wide instructions Op_rule, Op_func_call .. */
-		emalloc(cp, INSTRUCTION *, (size + 1) * sizeof(INSTRUCTION), "bcalloc");
-		cp->pool_size = size;
-		cp->nexti = pool_list->nexti;
-		pool_list->nexti = cp++;
+	if (pool->free_list != NULL) {
+		cp = pool->free_list;
+		pool->free_list = cp->nexti;
+	} else if (pool->free_space && pool->free_space + size <= & pool->block_list->i[INSTR_CHUNK]) {
+		cp = pool->free_space;
+		pool->free_space += size;
 	} else {
-		INSTRUCTION *pool;
-
-		pool = pool_list->freei;
-		if (pool == NULL) {
-			INSTRUCTION *last;
-			emalloc(cp, INSTRUCTION *, (INSTR_CHUNK + 1) * sizeof(INSTRUCTION), "bcalloc");
-
-			cp->pool_size = INSTR_CHUNK;
-			cp->nexti = pool_list->nexti;
-			pool_list->nexti = cp;
-			pool = ++cp;
-			last = &pool[INSTR_CHUNK - 1];
-			for (; cp <= last; cp++) {
-				cp->opcode = 0;
-				cp->nexti = cp + 1;
-			}
-			--cp;
-			cp->nexti = NULL;
-		}
-		cp = pool;
-		pool_list->freei = cp->nexti;
+		struct instruction_block *block;
+		emalloc(block, struct instruction_block *, sizeof(struct instruction_block), "bcalloc");
+		block->next = pool->block_list;
+		pool->block_list = block;
+		cp = &block->i[0];
+		pool->free_space = &block->i[size];
 	}
 
 	memset(cp, 0, size * sizeof(INSTRUCTION));
+	cp->pool_size = size;
 	cp->opcode = op;
 	cp->source_line = srcline;
 	return cp;
@@ -773,7 +772,7 @@ new_context()
 static void
 set_context(AWK_CONTEXT *ctxt)
 {
-	pool_list = & ctxt->pools;
+	pools = & ctxt->pools;
 	symbol_list = & ctxt->symbols;
 	srcfiles = & ctxt->srcfiles;
 	rule_list = & ctxt->rule_list;
@@ -912,27 +911,36 @@ free_bc_internal(INSTRUCTION *cp)
 	}
 }
 
-/* free_bcpool --- free list of instruction memory pools */
+/* free_bc_mempool --- free a single pool */
 
 static void
-free_bcpool(INSTRUCTION *pl)
+free_bc_mempool(struct instruction_mem_pool *pool, int size)
 {
-	INSTRUCTION *pool, *tmp;
+	bool first = true;
+	struct instruction_block *block, *next;
 
-	for (pool = pl->nexti; pool != NULL; pool = tmp) {
-		INSTRUCTION *cp, *last;
-		long psiz;
-		psiz = pool->pool_size;
-		if (psiz == INSTR_CHUNK)
-			last = pool + psiz;
-		else
-			last = pool + 1;
-		for (cp = pool + 1; cp <= last ; cp++) {
-			if (cp->opcode != 0)
+	for (block = pool->block_list; block; block = next) {
+		INSTRUCTION *cp, *end;
+
+		end = (first ? pool->free_space : & block->i[INSTR_CHUNK]);
+		for (cp = & block->i[0]; cp + size <= end; cp += size) {
+			if (cp->opcode != Op_illegal)
 				free_bc_internal(cp);
 		}
-		tmp = pool->nexti;
-		efree(pool);
+		next = block->next;
+		efree(block);
+		first = false;
 	}
-	memset(pl, 0, sizeof(INSTRUCTION));
+}
+
+
+/* free_bcpool --- free list of instruction memory pools */
+
+static void
+free_bcpool(INSTRUCTION_POOL *pl)
+{
+	int i;
+
+	for (i = 0; i < MAX_INSTRUCTION_ALLOC; i++)
+		free_bc_mempool(& pl->pool[i], i + 1);
 }
diff --git a/test/ChangeLog b/test/ChangeLog
index d684e73a..e1915002 100644
--- a/test/ChangeLog
+++ b/test/ChangeLog
@@ -1,3 +1,8 @@
+2017-04-12         Arnold D. Robbins     <arnold@skeeve.com>
+
+	* Makefile.am (memleak): New test.
+	* memleak.awk, memleak.ok: New files.
+
 2017-03-27         Arnold D. Robbins     <arnold@skeeve.com>
 
 	* fwtest4: Renamed from fwtest3.
diff --git a/test/Makefile.am b/test/Makefile.am
index b1a97621..686f4f0e 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -619,6 +619,8 @@ EXTRA_DIST = \
 	membug1.awk \
 	membug1.in \
 	membug1.ok \
+	memleak.awk \
+	memleak.ok \
 	messages.awk \
 	minusstr.awk \
 	minusstr.ok \
@@ -1190,7 +1192,7 @@ BASIC_TESTS = \
 	hex hex2 hsprint \
 	inpref inputred intest intprec iobug1 \
 	leaddig leadnl litoct longsub longwrds \
-	manglprm math membug1 messages minusstr mmap8k mtchi18n \
+	manglprm math membug1 memleak messages minusstr mmap8k mtchi18n \
 	nasty nasty2 negexp negrange nested nfldstr nfloop nfneg nfset nlfldsep \
 	nlinstr nlstrina noeffect nofile nofmtch noloop1 noloop2 nonl \
 	noparms nors nulinsrc nulrsend numindex numsubstr \
diff --git a/test/Makefile.in b/test/Makefile.in
index 57f5bf61..fd11ca4e 100644
--- a/test/Makefile.in
+++ b/test/Makefile.in
@@ -877,6 +877,8 @@ EXTRA_DIST = \
 	membug1.awk \
 	membug1.in \
 	membug1.ok \
+	memleak.awk \
+	memleak.ok \
 	messages.awk \
 	minusstr.awk \
 	minusstr.ok \
@@ -1447,7 +1449,7 @@ BASIC_TESTS = \
 	hex hex2 hsprint \
 	inpref inputred intest intprec iobug1 \
 	leaddig leadnl litoct longsub longwrds \
-	manglprm math membug1 messages minusstr mmap8k mtchi18n \
+	manglprm math membug1 memleak messages minusstr mmap8k mtchi18n \
 	nasty nasty2 negexp negrange nested nfldstr nfloop nfneg nfset nlfldsep \
 	nlinstr nlstrina noeffect nofile nofmtch noloop1 noloop2 nonl \
 	noparms nors nulinsrc nulrsend numindex numsubstr \
@@ -3324,6 +3326,11 @@ membug1:
 	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  < "$(srcdir)"/$@.in >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
 	@-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
 
+memleak:
+	@echo $@
+	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
+	@-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
+
 minusstr:
 	@echo $@
 	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
diff --git a/test/Maketests b/test/Maketests
index 9ff8ef90..a13c83e2 100644
--- a/test/Maketests
+++ b/test/Maketests
@@ -505,6 +505,11 @@ membug1:
 	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  < "$(srcdir)"/$@.in >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
 	@-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
 
+memleak:
+	@echo $@
+	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
+	@-$(CMP) "$(srcdir)"/$@.ok _$@ && rm -f _$@
+
 minusstr:
 	@echo $@
 	@AWKPATH="$(srcdir)" $(AWK) -f $@.awk  >_$@ 2>&1 || echo EXIT CODE: $$? >>_$@
diff --git a/test/memleak.awk b/test/memleak.awk
new file mode 100644
index 00000000..3937658f
--- /dev/null
+++ b/test/memleak.awk
@@ -0,0 +1,20 @@
+# This program doesn't do anything except allow us to
+# check for memory leak from using a user-supplied
+# sorting function.
+#
+# From Andrew Schorr.
+
+function my_func(i1, v1, i2, v2) {
+	return v2-v1
+}
+
+BEGIN {
+	a[1] = "3"
+	a[2] = "2"
+	a[3] = "4"
+	for (i = 0; i < 10000; i++) {
+		n = asort(a, b, "my_func")
+		s += n
+	}
+	print s
+}
diff --git a/test/memleak.ok b/test/memleak.ok
new file mode 100644
index 00000000..3a05c8b3
--- /dev/null
+++ b/test/memleak.ok
@@ -0,0 +1 @@
+30000