Improved talloc.c

[andreas moroder]

Hello,

as promised few weeks ago, I modified talloc.c to make it faster.
Instead of allocating two memory blocks, one for the list and one for the 
data I have only one malloc and a little bit of pointer arithemitcs. I made a 
few tests with the little program you find at the end of the mail and got 
this results

New routine 2.946 seconds, old 4.750 seconds ( for approx. 3.000.000 allocs )



If you set STEP_REALLOC lower ( much more reallocs ) , the proportional gain 
gets lower but the effective time difference remains.

talloc_realloc is all but efficent, but that's the next job.

In the comments there is the line "It guarantees memory of a TALLOC_ALIGN 
alignment", but how ? TALLOC_ALLIGN is never in the include files of samba.
If I find I will will use it instead the constat 8 I used.


Bye

Andreas

P.S. I posted four times different problems with mallocs without checks but I 
got only a answer after the first one. Is there anyone that did read them and 
wrote the patches ?




/*
   Unix SMB/Netbios implementation.
   Version 3.0
   Samba temporary memory allocation functions
   Copyright (C) Andrew Tridgell 2000

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

/* this is a very simple temporary memory allocator. To use it do the 
following:

   1) when you first want to allocate a pool of meomry use
   talloc_init() and save the resulting context pointer somewhere

   2) to allocate memory use talloc()

   3) when _all_ of the memory allocated using this context is no longer 
needed
   use talloc_destroy()

   talloc does not zero the memory. It guarantees memory of a
   TALLOC_ALIGN alignment
*/

static unsigned short tc_offset;

#include "includes.h"


/* initialise talloc context. */
TALLOC_CTX *talloc_init(void)
{
	TALLOC_CTX *t;
	unsigned short l, off;

	t = (TALLOC_CTX *)malloc(sizeof(*t));
	if (!t) return NULL;

	t->list = NULL;
	t->total_alloc_size = 0;

 /* Maybe there is a way to calculate the alligned size of this structure at 
compile time +/
 /* If there are systems that must allign on a bigger boundary, so the 
constant 8 must be changed */
	l=sizeof(struct talloc_chunk);
	for(tc_offset=0;l!=0; tc_offset+=8)
		l=l>>3;

	return t;
}

/* allocate a bit of memory from the specified pool */
void *talloc(TALLOC_CTX *t, size_t size)
{
	void *p;
	struct talloc_chunk *tc;

	if (size == 0) return NULL;

	tc = malloc(tc_offset+size);
	if (!tc) {
		free(p);
		return NULL;
	}

	p=(void *)tc;
	p+=tc_offset;
	tc->ptr = p;
	tc->size = size;
	tc->next = t->list;
	t->list = tc;
	t->total_alloc_size += size;

	return p;
}

/* a talloc version of realloc */
void *talloc_realloc(TALLOC_CTX *t, void *ptr, size_t size)
{
	struct talloc_chunk *tc, *prev,*next;
	void *p;

	/* size zero is equivalent to free() */
	if (size == 0)
		return NULL;

	/* realloc(NULL) is equavalent to malloc() */
	if (ptr == NULL)
		return talloc(t, size);

	prev=NULL;
	for (tc=t->list; tc; tc=tc->next) {
		if (tc->ptr == ptr) {
			next=tc->next;
			ptr = realloc(tc, size+tc_offset);
			if (ptr) {
				tc=ptr;
				p=(void *)tc;
				p+=tc_offset;
				tc->ptr = p;
				t->total_alloc_size += (size - tc->size);
				tc->size = size;

				if(prev) {
					prev->next=tc;
				} else	{
					t->list=tc;
				}
				ptr=p;
			} else {
				if(prev) {
					prev->next=next;
				} else	{
					t->list=next;
				}
				/* should I free the data pointed by original tc ? */
                                /* If I don't I am buggy but consistent with 
the rest of samba */
			}
			return ptr;
		}
		prev=tc;
	}
	return NULL;
}

/* destroy a whole pool */
void talloc_destroy_pool(TALLOC_CTX *t)
{
	struct talloc_chunk *c;

	if (!t)
		return;

	while (t->list) {
		c = t->list->next;
//		if (t->list->ptr) free(t->list->ptr);
		free(t->list);
		t->list = c;
	}

	t->list = NULL;
	t->total_alloc_size = 0;
}

/* destroy a whole pool including the context */
void talloc_destroy(TALLOC_CTX *t)
{
	if (!t)
		return;
	talloc_destroy_pool(t);
	memset(t, 0, sizeof(*t));
	free(t);
}

/* return the current total size of the pool. */
size_t talloc_pool_size(TALLOC_CTX *t)
{
	return t->total_alloc_size;
}

/* talloc and zero memory. */
void *talloc_zero(TALLOC_CTX *t, size_t size)
{
	void *p = talloc(t, size);

	if (p)
		memset(p, '\0', size);

	return p;
}

/* memdup with a talloc. */
void *talloc_memdup(TALLOC_CTX *t, void *p, size_t size)
{
	void *newp = talloc(t,size);

	if (!newp)
		return 0;

	memcpy(newp, p, size);

	return newp;
}

/* strdup with a talloc */
char *talloc_strdup(TALLOC_CTX *t, char *p)
{
	return talloc_memdup(t, p, strlen(p) + 1);
}



And thats the small prog i made to test and to check if realloc works as 
wanted.

#define STEP_REALLOC 10

#include "includes.h"

main()
{
	TALLOC_CTX *tcbase;
	struct talloc_chunk *tc;
	char *mem,*data,*temp;
	char *array[200];
	int i;
	int l;


        printf("chunk: %d\n",sizeof(struct talloc_chunk));
        for(l=1;l<30000;l++) {

	        tcbase=talloc_init();

	        if ( tcbase==NULL) {
                        printf("INIT FAILED");
                        return 10;
                }

                for(i=34;i<127;i++) {
                        mem=(char*)talloc(tcbase,100);
                        if (mem==NULL) {
                                printf("Alloc failed at %d\n",i);
                                i=1001;
                        }
                        array[i]=mem;
                        mem[0]='A';
                        mem[1]=(char) i;
                        mem[2]='B';
                        mem[3]=0;
                }

                for(i=34;i<127;i+=STEP_REALLOC) {
                        mem=(char*)talloc_realloc(tcbase,array[i],200);
                        if (mem==NULL) {
                                printf("Alloc failed at %d\n",i);
                                i=1001;
                        }
                        array[i]=mem;
                }

                tc=tcbase->list;
                for(i=126;tc ;i--) {
                        temp=(char *)tc->ptr;
                        if (temp[1]!=i) {
                                printf("ERROR at %d %d!!!\n",l,i);
                                i=1000;
                                l=35000;
                                tc->next=NULL;
                        }
                        tc=tc->next;
                }

                talloc_destroy(tcbase);
        }
}