From 070c57daec076e780e81d8b1011a02ea8ac8915f Mon Sep 17 00:00:00 2001 From: "Arnold D. Robbins" Date: Tue, 4 Apr 2017 21:53:44 +0300 Subject: fixes for memory leak for user-supplied sorting function. --- ChangeLog | 15 ++++++++++++ array.c | 28 +++++++++++----------- awk.h | 9 ++++++- symbol.c | 71 ++++++++++++++++---------------------------------------- test/memleak.awk | 20 ++++++++++++++++ 5 files changed, 77 insertions(+), 66 deletions(-) create mode 100644 test/memleak.awk diff --git a/ChangeLog b/ChangeLog index 6822c6f4..79262466 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,18 @@ +2017-04-04 Arnold D. Robbins + + * 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 Cause EPIPE errors to stdout to generate a real SIGPIPE. 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 c1e9b4a9..6b7cdb7a 100644 --- a/awk.h +++ b/awk.h @@ -783,6 +783,7 @@ typedef struct exp_instruction { } x; short source_line; + short pool_size; // memory management in symbol.c OPCODE opcode; } INSTRUCTION; @@ -1031,9 +1032,15 @@ 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 + INSTRUCTION pool[MAX_INSTRUCTION_ALLOC + 1]; +} 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..b2a6a6c2 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,19 @@ check_param_names(void) return result; } -#define pool_size d.dl #define freei x.xi -static INSTRUCTION *pool_list; - -/* INSTR_CHUNK must be > largest code size (3) */ -#define INSTR_CHUNK 127 +static INSTRUCTION_POOL pools; /* bcfree --- deallocate instruction */ void bcfree(INSTRUCTION *cp) { + assert(cp->pool_size >= 1 && cp->pool_size <= MAX_INSTRUCTION_ALLOC); + cp->opcode = 0; - cp->nexti = pool_list->freei; - pool_list->freei = cp; + cp->nexti = pools.pool[cp->pool_size].freei; + pools.pool[cp->pool_size].freei = cp; } /* bcalloc --- allocate a new instruction */ @@ -717,37 +715,16 @@ bcalloc(OPCODE op, int size, int srcline) { INSTRUCTION *cp; - 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++; + assert(size >= 1 && size <= MAX_INSTRUCTION_ALLOC); + + if ((cp = pools.pool[size].freei) != NULL) { + pools.pool[size].freei = cp->nexti; } 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; + emalloc(cp, INSTRUCTION *, (size + 1) * sizeof(INSTRUCTION), "bcalloc"); } memset(cp, 0, size * sizeof(INSTRUCTION)); + cp->pool_size = size; cp->opcode = op; cp->source_line = srcline; return cp; @@ -773,7 +750,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; @@ -915,24 +892,16 @@ free_bc_internal(INSTRUCTION *cp) /* free_bcpool --- free list of instruction memory pools */ static void -free_bcpool(INSTRUCTION *pl) +free_bcpool(INSTRUCTION_POOL *pl) { - INSTRUCTION *pool, *tmp; - - 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++) { + INSTRUCTION *cp, *next; + int i; + + for (i = 1; i <= MAX_INSTRUCTION_ALLOC; i++) { + for (cp = pl->pool[i].nexti; cp != NULL; cp = next) { + next = cp->nexti; if (cp->opcode != 0) free_bc_internal(cp); } - tmp = pool->nexti; - efree(pool); } - memset(pl, 0, sizeof(INSTRUCTION)); } 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 +} -- cgit v1.2.3 From 22bfbd1057c2fa9d5e5b2401d6b1ab60737452d9 Mon Sep 17 00:00:00 2001 From: "Andrew J. Schorr" Date: Fri, 7 Apr 2017 11:30:22 -0400 Subject: Patch INSTRUCTION allocator to malloc instruction blocks and eliminate leaks. --- ChangeLog | 15 ++++++++++++++ awk.h | 6 +++++- symbol.c | 71 +++++++++++++++++++++++++++++++++++++++++++++++++-------------- 3 files changed, 75 insertions(+), 17 deletions(-) diff --git a/ChangeLog b/ChangeLog index 79262466..ba5bba55 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,18 @@ +2017-04-07 Andrew J. Schorr + + * 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 * awk.h (INSTRUCTION): Add pool_size member. diff --git a/awk.h b/awk.h index 6b7cdb7a..c7bfec2b 100644 --- a/awk.h +++ b/awk.h @@ -1035,7 +1035,11 @@ typedef struct 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 - INSTRUCTION pool[MAX_INSTRUCTION_ALLOC + 1]; + 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 */ diff --git a/symbol.c b/symbol.c index b2a6a6c2..d63277b1 100644 --- a/symbol.c +++ b/symbol.c @@ -693,8 +693,19 @@ check_param_names(void) return result; } -#define freei x.xi -static INSTRUCTION_POOL pools; +static INSTRUCTION_POOL *pools; + +/* + * 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 */ @@ -704,8 +715,8 @@ bcfree(INSTRUCTION *cp) assert(cp->pool_size >= 1 && cp->pool_size <= MAX_INSTRUCTION_ALLOC); cp->opcode = 0; - cp->nexti = pools.pool[cp->pool_size].freei; - pools.pool[cp->pool_size].freei = cp; + cp->nexti = pools->pool[cp->pool_size - 1].free_list; + pools->pool[cp->pool_size - 1].free_list = cp; } /* bcalloc --- allocate a new instruction */ @@ -714,13 +725,24 @@ INSTRUCTION * bcalloc(OPCODE op, int size, int srcline) { INSTRUCTION *cp; + struct instruction_mem_pool *pool; assert(size >= 1 && size <= MAX_INSTRUCTION_ALLOC); - - if ((cp = pools.pool[size].freei) != NULL) { - pools.pool[size].freei = cp->nexti; + pool = &pools->pool[size - 1]; + + 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 { - emalloc(cp, INSTRUCTION *, (size + 1) * sizeof(INSTRUCTION), "bcalloc"); + 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)); @@ -750,7 +772,7 @@ new_context() static void set_context(AWK_CONTEXT *ctxt) { - pools = ctxt->pools; + pools = & ctxt->pools; symbol_list = & ctxt->symbols; srcfiles = & ctxt->srcfiles; rule_list = & ctxt->rule_list; @@ -889,19 +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_POOL *pl) +free_bc_mempool(struct instruction_mem_pool *pool, int size) { - INSTRUCTION *cp, *next; - int i; + int first = 1; + struct instruction_block *block, *next; - for (i = 1; i <= MAX_INSTRUCTION_ALLOC; i++) { - for (cp = pl->pool[i].nexti; cp != NULL; cp = next) { - next = cp->nexti; + 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 != 0) free_bc_internal(cp); } + next = block->next; + efree(block); + first = 0; } } + + +/* 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); +} -- cgit v1.2.3 From 38bf60d89b766be81789ddd47c2e237c2af4710e Mon Sep 17 00:00:00 2001 From: "Arnold D. Robbins" Date: Mon, 10 Apr 2017 15:08:32 +0300 Subject: Small style change in symbol.c. --- ChangeLog | 4 ++++ symbol.c | 4 ++-- 2 files changed, 6 insertions(+), 2 deletions(-) diff --git a/ChangeLog b/ChangeLog index ba5bba55..daa1bbde 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,7 @@ +2017-04-10 Arnold D. Robbins + + * symbol.c (free_bc_mempool): Change `first' from int to bool. + 2017-04-07 Andrew J. Schorr * awk.h (INSTRUCTION_POOL): Redefine as an array of structures so we diff --git a/symbol.c b/symbol.c index d63277b1..51e3cf23 100644 --- a/symbol.c +++ b/symbol.c @@ -916,7 +916,7 @@ free_bc_internal(INSTRUCTION *cp) static void free_bc_mempool(struct instruction_mem_pool *pool, int size) { - int first = 1; + bool first = true; struct instruction_block *block, *next; for (block = pool->block_list; block; block = next) { @@ -929,7 +929,7 @@ free_bc_mempool(struct instruction_mem_pool *pool, int size) } next = block->next; efree(block); - first = 0; + first = false; } } -- cgit v1.2.3 From 887477763ab87b33c06df693e93500991d7c324d Mon Sep 17 00:00:00 2001 From: "Andrew J. Schorr" Date: Mon, 10 Apr 2017 12:04:25 -0400 Subject: Use Op_illegal instead of 0 in a couple of places for greater clarity. --- ChangeLog | 9 +++++++++ awk.h | 3 +-- symbol.c | 4 ++-- 3 files changed, 12 insertions(+), 4 deletions(-) diff --git a/ChangeLog b/ChangeLog index daa1bbde..744443f0 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2017-04-10 Andrew J. Schorr + + * 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. + 2017-04-10 Arnold D. Robbins * symbol.c (free_bc_mempool): Change `first' from int to bool. diff --git a/awk.h b/awk.h index c7bfec2b..5cad2044 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, diff --git a/symbol.c b/symbol.c index 51e3cf23..ea5ee0af 100644 --- a/symbol.c +++ b/symbol.c @@ -714,7 +714,7 @@ bcfree(INSTRUCTION *cp) { assert(cp->pool_size >= 1 && cp->pool_size <= MAX_INSTRUCTION_ALLOC); - cp->opcode = 0; + cp->opcode = Op_illegal; cp->nexti = pools->pool[cp->pool_size - 1].free_list; pools->pool[cp->pool_size - 1].free_list = cp; } @@ -924,7 +924,7 @@ free_bc_mempool(struct instruction_mem_pool *pool, int size) end = (first ? pool->free_space : & block->i[INSTR_CHUNK]); for (cp = & block->i[0]; cp + size <= end; cp += size) { - if (cp->opcode != 0) + if (cp->opcode != Op_illegal) free_bc_internal(cp); } next = block->next; -- cgit v1.2.3 From 906ac1a525dd0f7ad87bafdaf882323938842760 Mon Sep 17 00:00:00 2001 From: "Arnold D. Robbins" Date: Wed, 12 Apr 2017 11:44:15 +0300 Subject: Add new memleak test. --- test/ChangeLog | 5 +++++ test/Makefile.am | 4 +++- test/Makefile.in | 9 ++++++++- test/Maketests | 5 +++++ test/memleak.ok | 1 + 5 files changed, 22 insertions(+), 2 deletions(-) create mode 100644 test/memleak.ok 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 + + * Makefile.am (memleak): New test. + * memleak.awk, memleak.ok: New files. + 2017-03-27 Arnold D. Robbins * 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.ok b/test/memleak.ok new file mode 100644 index 00000000..3a05c8b3 --- /dev/null +++ b/test/memleak.ok @@ -0,0 +1 @@ +30000 -- cgit v1.2.3