Optimize the halloc implementation so that mutiple calls to halloc can be satisfied by a single malloc, also add wcsdup and wcsndup workalikes using halloc

darcs-hash:20060211001317-ac50b-c9cf234c334b4d697fe1251c21013c8ec7f7b0a1.gz

9 files changed, 157 insertions, 40 deletions

diff --git a/builtin.c b/builtin.c
index cb3d9fac..5089765a 100644
--- a/builtin.c
+++ b/builtin.c
@@ -1037,7 +1037,7 @@ static int builtin_function( wchar_t **argv )
 				if( !e )
 					die_mem();
 				e->type = EVENT_VARIABLE;
-				e->param1.variable = halloc_register( current_block, wcsdup( woptarg ));
+				e->param1.variable = halloc_wcsdup( current_block, woptarg );
 				e->function_name=0;
 				al_push( events, e );
 				break;
@@ -1201,8 +1201,8 @@ static int builtin_function( wchar_t **argv )
 	}
 	else
 	{
-		current_block->param1.function_name=halloc_register( current_block, wcsdup(argv[woptind]));
-		current_block->param2.function_description=desc?halloc_register( current_block, wcsdup(desc)):0;
+		current_block->param1.function_name=halloc_wcsdup( current_block, argv[woptind]);
+		current_block->param2.function_description=desc?halloc_wcsdup( current_block, desc):0;
 		current_block->param3.function_is_binding = is_binding;
 		current_block->param4.function_events = events;
 		
@@ -2579,11 +2579,11 @@ static int builtin_for( wchar_t **argv )
 
 		int i;
 		current_block->tok_pos = parser_get_pos();
-		current_block->param1.for_variable = halloc_register( current_block, wcsdup( argv[1] ));
+		current_block->param1.for_variable = halloc_wcsdup( current_block, argv[1] );
 
 		for( i=argc-1; i>3; i-- )
 		{
-			al_push( &current_block->param2.for_vars, halloc_register( current_block, wcsdup(argv[ i ] ) ) );
+			al_push( &current_block->param2.for_vars, halloc_wcsdup( current_block, argv[ i ] ) );
 		}
 		halloc_register( current_block, current_block->param2.for_vars.arr );
 
@@ -2899,7 +2899,7 @@ static int builtin_switch( wchar_t **argv )
 	else
 	{
 		parser_push_block( SWITCH );
-		current_block->param1.switch_value = halloc_register( current_block, wcsdup( argv[1]));
+		current_block->param1.switch_value = halloc_wcsdup( current_block, argv[1]);
 		current_block->skip=1;
 		current_block->param2.switch_taken=0;
 	}
diff --git a/common.h b/common.h
index 8ab2ba9d..4208291c 100644
--- a/common.h
+++ b/common.h
@@ -270,8 +270,7 @@ void debug( int level, const wchar_t *msg, ... );
    \return The escaped string, or 0 if there is not enough memory
 */
 
-wchar_t *escape( const wchar_t *in, 
-				 int escape_all );
+wchar_t *escape( const wchar_t *in, int escape_all );
 
 /**
    Expand backslashed escapes and substitute them with their unescaped
diff --git a/complete.c b/complete.c
index a2a73233..c6e218ea 100644
--- a/complete.c
+++ b/complete.c
@@ -380,7 +380,6 @@ void complete_add( const wchar_t *cmd,
 		if( !(c = malloc( sizeof(complete_entry) )))
 			die_mem();
 
-
 		c->next = first_entry;
 		first_entry = c;
 
diff --git a/halloc.c b/halloc.c
index 95000d02..3779f99b 100644
--- a/halloc.c
+++ b/halloc.c
@@ -15,9 +15,22 @@
 #include "common.h"
 #include "halloc.h"
 
+#define HALLOC_BLOCK_SIZE 256
+#define HALLOC_SCRAP_SIZE 16
+
+static int child_count=0;
+static int child_size=0;
+static int alloc_count =0;
+static int alloc_spill = 0;
+static pid_t pid=0;
+static int parent_count=0;
+
+
 typedef struct halloc
 {
 	array_list_t children;
+	void *scratch;
+	size_t scratch_free;
 	long long data[0];
 }
 	halloc_t;
@@ -27,26 +40,80 @@ static halloc_t *halloc_from_data( void *data )
 	return (halloc_t *)(data - sizeof( halloc_t ) );
 }
 
+static void late_free( void *data)
+{
+}
+
+static void woot()
+{
+	if( getpid() == pid )
+	{
+		debug( 1, L"%d parents, %d children with average child size of %.2f bytes caused %d allocs, average spill of %.2f bytes", 
+			   parent_count, child_count, (double)child_size/child_count,
+			   parent_count+alloc_count, (double)alloc_spill/(parent_count+alloc_count) );				
+	}
+}
 
 void *halloc( void *context, size_t size )
 {	
 	halloc_t *me, *parent;
-	
-	me = (halloc_t *)calloc( 1, sizeof(halloc_t) + size );
-	
-	if( !me )
-		return 0;
-	
-	al_init( &me->children );
-	
 	if( context )
-	{		
+	{
+		void *res;
+		
+			
+		if( !child_count )
+		{
+			pid = getpid();
+			atexit( woot );
+		}
+		
+		child_count++;
+		child_size += size;
+		
 		parent = halloc_from_data( context );
-		al_push( &parent->children, &halloc_free );
-		al_push( &parent->children, &me->data );
-	}
+		if( size <= parent->scratch_free )
+		{
+			res = parent->scratch;
+			parent->scratch_free -= size;
+			parent->scratch += size;
+		}
+		else
+		{
+			alloc_count++;
+			
+			if( parent->scratch_free < HALLOC_SCRAP_SIZE )
+			{
+				alloc_spill += parent->scratch_free;
+				res = calloc( 1, size + HALLOC_BLOCK_SIZE );
+				parent->scratch = res + size;
+				parent->scratch_free = HALLOC_BLOCK_SIZE;
+			}
+			else
+			{
+				res = calloc( 1, size );
+			}
+			al_push( &parent->children, &late_free );
+			al_push( &parent->children, res );
+			
+		}
+		return res;
 	
-	return &me->data;
+	}
+	else
+	{
+		me = (halloc_t *)calloc( 1, sizeof(halloc_t) + size + HALLOC_BLOCK_SIZE );
+		
+		if( !me )
+			return 0;
+		parent_count++;
+		
+		me->scratch = ((void *)me) + sizeof(halloc_t) + size;
+		me->scratch_free = HALLOC_BLOCK_SIZE;
+		
+		al_init( &me->children );
+		return &me->data;
+	}
 }
 
 void halloc_register_function( void *context, void (*func)(void *), void *data )
@@ -67,13 +134,25 @@ void halloc_free( void *context )
 	
 	if( !context )
 		return;
+
 	
 	me = halloc_from_data( context );
+
+	alloc_spill += me->scratch_free;
+
+	for( i=0; i<al_get_count(&me->children); i+=2 )
+	{
+		void (*func)(void *) = (void (*)(void *))al_get( &me->children, i );
+		void * data = (void *)al_get( &me->children, i+1 );
+		if( func != &late_free )
+			func( data );
+	}
 	for( i=0; i<al_get_count(&me->children); i+=2 )
 	{
 		void (*func)(void *) = (void (*)(void *))al_get( &me->children, i );
 		void * data = (void *)al_get( &me->children, i+1 );
-		func( data );
+		if( func == &late_free )
+			free( data );
 	}
 	al_destroy( &me->children );
 	free(me);
diff --git a/halloc.h b/halloc.h
index 6dfdb4e2..33d3dc16 100644
--- a/halloc.h
+++ b/halloc.h
@@ -1,6 +1,6 @@
 /** \file halloc.h 
 
-    A hierarchical memory allocation system. Works just like talloc
+    A hierarchical memory allocation system. Works mostly like talloc
 	used in Samba, except that an arbitrary block allocated with
 	malloc() can be registered to be freed by halloc_free.
 
@@ -13,23 +13,33 @@
    Allocate new memory using specified parent memory context. Context
    _must_ be either 0 or the result of a previous call to halloc.
 
-   If \c context is null, the resulting block is a root context, and
+   If \c context is null, the resulting block is a root block, and
    must be freed with a call to halloc_free().
 
-   If \c context is not null, the resulting memory block is a child
-   context, and must never be explicitly freed, it will be
-   automatically freed whenever the parent context is freed.
+   If \c context is not null, context must be a halloc root block. the
+   resulting memory block is a child context, and must never be
+   explicitly freed, it will be automatically freed whenever the
+   parent context is freed. Child blocks can never be used as the
+   context in calls to halloc_register_function, halloc_free, etc.
 */
 void *halloc( void *context, size_t size );
 
 /**
    Make the specified function run whenever context is free'd, using data as argument.
+
+   \c context a halloc root block
 */
 void halloc_register_function( void *context, void (*func)(void *), void *data );
 
 /**
    Free memory context and all children contexts. Only root contexts
    may be freed explicitly.
+
+   All functions registered with halloc_register_function are run in
+   the order they where added. Afterwards, all memory allocated using
+   halloc itself is free'd.
+
+   \c context a halloc root block
 */
 void halloc_free( void *context );
 
diff --git a/halloc_util.c b/halloc_util.c
index bc575f7e..f2eae06a 100644
--- a/halloc_util.c
+++ b/halloc_util.c
@@ -10,6 +10,7 @@
 
 #include <stdlib.h>
 #include <unistd.h>
+#include <string.h>
 
 #include "util.h"
 #include "common.h"
@@ -33,7 +34,7 @@ array_list_t *al_halloc( void *context )
 	if( !res )
 		die_mem();
 	al_init( res );
-	halloc_register_function( res, (void (*)(void *)) &al_destroy, res );
+	halloc_register_function( context, (void (*)(void *)) &al_destroy, res );
 	return res;
 }
 
@@ -43,7 +44,7 @@ string_buffer_t *sb_halloc( void *context )
 	if( !res )
 		die_mem();
 	sb_init( res );
-	halloc_register_function( res, (void (*)(void *)) &sb_destroy, res );
+	halloc_register_function( context, (void (*)(void *)) &sb_destroy, res );
 	return res;
 }
 
@@ -67,3 +68,27 @@ void *halloc_register( void *context, void *data )
 	return data;
 }
 
+wchar_t *halloc_wcsdup( void *context, wchar_t *in )
+{
+	size_t len=wcslen(in);
+	wchar_t *out = halloc( context, sizeof( wchar_t)*(len+1));
+	
+	if( out == 0 )
+	{
+		die_mem();
+	}
+	memcpy( out, in, sizeof( wchar_t)*(len+1));
+	return out;
+}
+
+wchar_t *halloc_wcsndup( void * context, const wchar_t *in, int c )
+{
+	wchar_t *res = halloc( context, sizeof(wchar_t)*(c+1) );
+	if( res == 0 )
+	{
+		die_mem();
+	}
+	wcslcpy( res, in, c );
+	res[c] = L'\0';	
+	return res;	
+}
diff --git a/halloc_util.h b/halloc_util.h
index c58dff20..8ff911bf 100644
--- a/halloc_util.h
+++ b/halloc_util.h
@@ -26,4 +26,10 @@ void halloc_register_function_void( void *context, void (*func)() );
    using a call to halloc() can be used as a context.
 */
 void *halloc_register( void *context, void *data );
+
+wchar_t *halloc_wcsdup( void *context, wchar_t *str );
+wchar_t *halloc_wcsndup( void * context, const wchar_t *in, int c );
+
+
+
 #endif
diff --git a/history.c b/history.c
index aa8d9f78..ae1da878 100644
--- a/history.c
+++ b/history.c
@@ -19,6 +19,7 @@
 #include "reader.h"
 #include "env.h"
 #include "sanity.h"
+#include "signal.h"
 
 /*
   The history is implemented using a linked list. Searches are done
diff --git a/parser.c b/parser.c
index 3db7b4b0..6b5a61a5 100644
--- a/parser.c
+++ b/parser.c
@@ -1321,8 +1321,7 @@ static void parse_job_main_loop( process_t *p,
 					return;
 				}
 				p->pipe_fd = wcstol( tok_last( tok ), 0, 10 );
-				p->argv = list_to_char_arr( args );
-				halloc_register( j, p->argv );
+				halloc_register( j, p->argv=list_to_char_arr( args ) );
 				p->next = halloc( j, sizeof( process_t ) );
 				if( p->next == 0 )
 				{
@@ -1344,8 +1343,7 @@ static void parse_job_main_loop( process_t *p,
 
 			case TOK_END:
 			{
-				p->argv = list_to_char_arr( args );
-				halloc_register( j, p->argv );
+				halloc_register( j, p->argv=list_to_char_arr( args ) );
 				if( tok_has_next(tok))
 					tok_next(tok);
 
@@ -1412,7 +1410,7 @@ static void parse_job_main_loop( process_t *p,
 							unmatched_wildcard = 1;
 							if( !unmatched )
 							{
-								unmatched = halloc_register( j, wcsdup( tok_last( tok )));
+								unmatched = halloc_wcsdup( j, tok_last( tok ));
 								unmatched_pos = tok_get_pos( tok );
 							}
 
@@ -2034,9 +2032,8 @@ static int parse_job( process_t *p,
 	if( !error_code )
 	{
 		if( p->type == INTERNAL_BUILTIN && parser_skip_arguments( (wchar_t *)al_get(args, 0) ) )
-		{
-			p->argv = list_to_char_arr( args );
-			halloc_register( j, p->argv );
+		{			
+			halloc_register( j, p->argv = list_to_char_arr( args ) );
 //			tok_next(tok);
 		}
 		else
@@ -2173,8 +2170,9 @@ static void eval_job( tokenizer *tok )
 					if( newline )
 						stop_pos = mini( stop_pos, newline - tok_string(tok) );
 
-					j->command = halloc_register( j, wcsndup( tok_string(tok)+start_pos,
-														   stop_pos-start_pos ));
+					j->command = halloc_wcsndup( j,
+												 tok_string(tok)+start_pos,
+												 stop_pos-start_pos );
 				}
 				else
 					j->command = L"";