r1983: a completely new implementation of talloc

This version does the following:

  1) talloc_free(), talloc_realloc() and talloc_steal() lose their
     (redundent) first arguments

  2) you can use _any_ talloc pointer as a talloc context to allocate
     more memory. This allows you to create complex data structures
     where the top level structure is the logical parent of the next
     level down, and those are the parents of the level below
     that. Then destroy either the lot with a single talloc_free() or
     destroy any sub-part with a talloc_free() of that part

  3) you can name any pointer. Use talloc_named() which is just like
     talloc() but takes the printf style name argument as well as the
     parent context and the size.

The whole thing ends up being a very simple piece of code, although
some of the pointer walking gets hairy.

So far, I'm just using the new talloc() like the old one. The next
step is to actually take advantage of the new interface
properly. Expect some new commits soon that simplify some common
coding styles in samba4 by using the new talloc().
(This used to be commit e35bb094c52e550b3105dd1638d8d90de71d854f)

1 files changed, 199 insertions, 358 deletions

diff --git a/source4/lib/talloc.c b/source4/lib/talloc.c
index 21c3bdac6e..8a67f83a7f 100644
--- a/source4/lib/talloc.c
+++ b/source4/lib/talloc.c
@@ -1,8 +1,9 @@
 /* 
    Samba Unix SMB/CIFS implementation.
-   Samba temporary memory allocation functions
-   Copyright (C) Andrew Tridgell 2000-2004
-   Copyright (C) 2001, 2002 by Martin Pool <mbp@samba.org>
+
+   Samba temporary memory allocation functions - new interface
+
+   Copyright (C) Andrew Tridgell 2004
    
    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
@@ -19,208 +20,175 @@
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
 
-/**
-   @defgroup talloc Simple memory allocator
-   @{
-   
-   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. 
-
-   @sa talloc.h
-*/
-
-/**
- * If you want testing for memory corruption use valgrind
- **/
-
 #include "includes.h"
 
 #define MAX_TALLOC_SIZE 0x10000000
-#define TALLOC_MAGIC 0x06052004
+#define TALLOC_MAGIC 0x14082004
 #define TALLOC_MAGIC_FREE 0x3421abcd
 
 struct talloc_chunk {
 	struct talloc_chunk *next, *prev;
-	TALLOC_CTX *context;
+	struct talloc_chunk *parent, *child;
 	size_t size;
-	void *ptr;
 	uint_t magic;
+	char *name;
 };
 
 
-struct talloc_ctx {
-	struct talloc_chunk *list;
-	off_t total_alloc_size;
-
-	/** The name recorded for this pool, if any.  Should describe
-	 * the purpose for which it was allocated.  The string is
-	 * allocated within the pool. **/
-	char *name;
+/* 
+   Allocate a bit of memory as a child of an existing pointer
+*/
+void *talloc(void *context, size_t size)
+{
+	struct talloc_chunk *tc;
 
-	/** Pointer to the next allocate talloc pool, so that we can
-	 * summarize all talloc memory usage. **/
-	struct talloc_ctx *next, *prev;
-};
+	if (size >= MAX_TALLOC_SIZE) {
+		return NULL;
+	}
 
+	tc = malloc(sizeof(*tc)+size);
+	if (tc == NULL) {
+		return NULL;
+	}
 
-/**
- * Start of linked list of all talloc pools.
- *
- * @todo We should turn the global list off when using Insure++,
- * otherwise all the memory will be seen as still reachable.
- **/
-static TALLOC_CTX *list_head;
+	tc->size = size;
+	tc->magic = TALLOC_MAGIC;
+	tc->child = NULL;
+	tc->name = NULL;
 
-/**
- * Add to the global list
- **/
-static void talloc_enroll(TALLOC_CTX *t)
-{
-#if 0
-	/* disabled enrole/disenrole until we have __thread support */
-	MUTEX_LOCK_BY_ID(MUTEX_TALLOC);
-	DLIST_ADD(list_head, t);
-	MUTEX_UNLOCK_BY_ID(MUTEX_TALLOC);
-#endif
-}
+	if (context) {
+		struct talloc_chunk *parent = ((struct talloc_chunk *)context)-1;
 
+		if (parent->magic != TALLOC_MAGIC) {
+			DEBUG(0,("Bad magic in context - 0x%08x\n", parent->magic));
+			free(tc);
+			return NULL;
+		}
 
-static void talloc_disenroll(TALLOC_CTX *t)
-{
-#if 0
-	/* disabled enrole/disenrole until we have __thread support */
-	MUTEX_LOCK_BY_ID(MUTEX_TALLOC);
-	DLIST_REMOVE(list_head, t);
-	MUTEX_UNLOCK_BY_ID(MUTEX_TALLOC);
-#endif
-}
+		tc->parent = parent;
 
+		if (parent->child) {
+			parent->child->parent = NULL;
+		}
 
-/** Create a new talloc context. **/
-static TALLOC_CTX *talloc_init_internal(void)
-{
-	TALLOC_CTX *t;
-
-	t = (TALLOC_CTX *)malloc(sizeof(TALLOC_CTX));
-	if (t) {
-		t->list = NULL;
-		t->total_alloc_size = 0;
-		t->name = NULL;
-		talloc_enroll(t);
+		DLIST_ADD(parent->child, tc);
+	} else {
+		tc->next = tc->prev = tc->parent = NULL;
 	}
 
-	return t;
+	return (void *)(tc+1);
 }
 
 
-
-/**
- * Create a new talloc context, with a name specifying its purpose.
- **/
-
- TALLOC_CTX *talloc_init(char const *fmt, ...) 
+/*
+  create a named talloc pointer
+*/
+void *talloc_named(void *context, size_t size, 
+		   const char *fmt, ...) _PRINTF_ATTRIBUTE(3,4)
 {
-	TALLOC_CTX *t;
 	va_list ap;
+	void *ptr;
+	struct talloc_chunk *tc;
 
-	t = talloc_init_internal();
-	if (t && fmt) {
-		/*
-		 * t->name must not be talloced.
-		 * as destroying the pool would destroy it. JRA.
-		 */
-		t->name = NULL;
-		va_start(ap, fmt);
-		vasprintf(&t->name, fmt, ap);
-		va_end(ap);
-		if (!t->name) {
-			talloc_destroy(t);
-			t = NULL;
-		}
+	ptr = talloc(context, size);
+	if (ptr == NULL) {
+		return NULL;
 	}
-	
-	return t;
-}
 
+	tc = ((struct talloc_chunk *)ptr)-1;
+
+	va_start(ap, fmt);
+	vasprintf(&tc->name, fmt, ap);
+	va_end(ap);
+
+	return ptr;
+}
 
 /*
-  return the talloc context given a pointer that has been allocated using
-  talloc
+  this is for compatibility with older versions of talloc
 */
-TALLOC_CTX *talloc_get_context(void *ptr)
+void *talloc_init(const char *fmt, ...) _PRINTF_ATTRIBUTE(1,2)
 {
+	va_list ap;
+	void *ptr;
 	struct talloc_chunk *tc;
-	tc = ((struct talloc_chunk *)ptr)-1;
 
-	if (tc->magic == TALLOC_MAGIC) {
-		return tc->context;
-	} else {
+	ptr = talloc(NULL, 0);
+	if (ptr == NULL) {
 		return NULL;
 	}
+
+	tc = ((struct talloc_chunk *)ptr)-1;
+
+	va_start(ap, fmt);
+	vasprintf(&tc->name, fmt, ap);
+	va_end(ap);
+
+	return ptr;
 }
 
-/** Allocate a bit of memory from the specified pool **/
-void *talloc(TALLOC_CTX *t, size_t size)
+
+
+/* 
+   free a talloc pointer. This also frees all child pointers of this 
+   pointer recursively
+*/
+void talloc_free(void *ptr)
 {
 	struct talloc_chunk *tc;
 
-	if (!t || size == 0) {
-		return NULL;
-	}
+	if (ptr == NULL) return;
 
-	tc = malloc(sizeof(*tc)+size);
-	if (!tc) {
-		return NULL;
+	tc = ((struct talloc_chunk *)ptr)-1;
+
+	if (tc->magic != TALLOC_MAGIC) {
+		DEBUG(0,("Bad talloc magic 0x%08x in talloc_free\n", tc->magic));
+		return;
 	}
 
-	tc->context = t;
-	tc->size = size;
-	tc->magic = TALLOC_MAGIC;
+	while (tc->child) {
+		talloc_free(tc->child + 1);
+	}
 
-	DLIST_ADD(t->list, tc);
+	if (tc->parent) {
+		DLIST_REMOVE(tc->parent->child, tc);
+		if (tc->parent->child) {
+			tc->parent->child->parent = tc->parent;
+		}
+	} else {
+		if (tc->prev) tc->prev->next = tc->next;
+		if (tc->next) tc->next->prev = tc->prev;
+	}
 
-	t->total_alloc_size += size;
+	tc->magic = TALLOC_MAGIC_FREE;
+	if (tc->name) free(tc->name);
 
-	return (void *)(tc+1);
+	free(tc);
 }
 
-/** A talloc version of realloc */
-void *talloc_realloc(TALLOC_CTX *t, void *ptr, size_t size)
+
+
+/*
+  A talloc version of realloc 
+*/
+void *talloc_realloc(void *ptr, size_t size)
 {
 	struct talloc_chunk *tc;
 	void *new_ptr;
 
 	/* size zero is equivalent to free() */
-	if (!t) {
-		return NULL;
-	}
-
 	if (size == 0) {
-		talloc_free(t, ptr);
+		talloc_free(ptr);
 		return NULL;
 	}
 
 	/* realloc(NULL) is equavalent to malloc() */
 	if (ptr == NULL) {
-		return talloc(t, size);
+		return talloc(NULL, size);
 	}
 
 	tc = ((struct talloc_chunk *)ptr)-1;
 
-	if (tc->context != t) {
-		DEBUG(0,("Bad talloc context passed to talloc_realloc\n"));
-		return NULL;
-	}
-
 	if (tc->magic != TALLOC_MAGIC) {
 		DEBUG(0,("Bad talloc magic 0x%08x in talloc_realloc\n", tc->magic));
 		return NULL;
@@ -235,11 +203,11 @@ void *talloc_realloc(TALLOC_CTX *t, void *ptr, size_t size)
 		return NULL;
 	}
 
-	if (tc == t->list) {
-		t->list = new_ptr;
-	}
 	tc = new_ptr;
 	tc->magic = TALLOC_MAGIC;
+	if (tc->parent) {
+		tc->parent->child = new_ptr;
+	}
 
 	if (tc->prev) {
 		tc->prev->next = tc;
@@ -248,129 +216,74 @@ void *talloc_realloc(TALLOC_CTX *t, void *ptr, size_t size)
 		tc->next->prev = tc;
 	}
 
-	t->total_alloc_size += (size - tc->size);
 	tc->size = size;
 
 	return (void *)(tc+1);
 }
 
 /* 
-   free a lump from a pool. Use sparingly please.
+   move a lump of memory from one talloc context to another return the
+   ptr on success, or NUL if it could not be transferred
 */
-void talloc_free(TALLOC_CTX *ctx, void *ptr)
+void *talloc_steal(void *new_ctx, void *ptr)
 {
-	struct talloc_chunk *tc;
-
-	if (!ptr || !ctx->list) return;
-
-	tc = ((struct talloc_chunk *)ptr)-1;
-
-	if (tc->context != ctx) {
-		DEBUG(0,("Bad talloc context passed to talloc_free\n"));
-	}
-
-	if (tc->magic != TALLOC_MAGIC) {
-		DEBUG(0,("Bad talloc magic 0x%08x in talloc_free\n", tc->magic));
-	}
-
-	DLIST_REMOVE(ctx->list, tc);
-
-	ctx->total_alloc_size -= tc->size;
-	tc->magic = TALLOC_MAGIC_FREE;
-
-	free(tc);
-}
-
-
-/* 
-   move a lump of memory from one talloc context to another
-   return the ptr on success, or NULL if it could not be found
-   in the old context or could not be transferred
-*/
-void *talloc_steal(TALLOC_CTX *old_ctx, TALLOC_CTX *new_ctx, void *ptr)
-{
-	struct talloc_chunk *tc;
+	struct talloc_chunk *tc, *new_tc;
 
 	if (!ptr) {
 		return NULL;
 	}
 
 	tc = ((struct talloc_chunk *)ptr)-1;
-
-	if (tc->context != old_ctx) {
-		DEBUG(0,("Bad talloc context passed to talloc_steal\n"));
-		return NULL;
-	}
+	new_tc = ((struct talloc_chunk *)new_ctx)-1;
 
 	if (tc->magic != TALLOC_MAGIC) {
 		DEBUG(0,("Bad talloc magic 0x%08x in talloc_steal\n", tc->magic));
 		return NULL;
 	}
-
-	DLIST_REMOVE(old_ctx->list, tc);
-	DLIST_ADD(new_ctx->list, tc);
-
-	tc->context = new_ctx;
-
-	old_ctx->total_alloc_size -= tc->size;
-	new_ctx->total_alloc_size += tc->size;
-	
-	return ptr;
-}
-
-
-
-/** Destroy all the memory allocated inside @p t, but not @p t
- * itself. */
-void talloc_destroy_pool(TALLOC_CTX *t)
-{
-	if (!t) {
-		return;
+	if (new_tc->magic != TALLOC_MAGIC) {
+		DEBUG(0,("Bad new talloc magic 0x%08x in talloc_steal\n", new_tc->magic));
+		return NULL;
 	}
 
-	while (t->list) {
-		struct talloc_chunk *tc = t->list;
-		if (tc->magic != TALLOC_MAGIC) {
-			DEBUG(0,("Bad magic 0x%08x in talloc_destroy_pool\n", 
-				 tc->magic));
-			return;
+	if (tc->parent) {
+		DLIST_REMOVE(tc->parent->child, tc);
+		if (tc->parent->child) {
+			tc->parent->child->parent = tc->parent;
 		}
-		DLIST_REMOVE(t->list, tc);
-		tc->magic = TALLOC_MAGIC_FREE;
-		free(tc);
+	} else {
+		if (tc->prev) tc->prev->next = tc->next;
+		if (tc->next) tc->next->prev = tc->prev;
 	}
 
-	t->total_alloc_size = 0;
-}
-
-/** Destroy a whole pool including the context */
-void talloc_destroy(TALLOC_CTX *t)
-{
-	if (!t)
-		return;
+	tc->parent = new_tc;
+	if (new_tc->child) new_tc->child->parent = NULL;
+	DLIST_ADD(new_tc->child, tc);
 
-	talloc_destroy_pool(t);
-	talloc_disenroll(t);
-	SAFE_FREE(t->name);
-	SAFE_FREE(t);
+	return ptr;
 }
 
-/** Return the current total size of the pool. */
-size_t talloc_pool_size(TALLOC_CTX *t)
+/*
+  return the total size of a talloc pool (subtree)
+*/
+off_t talloc_total_size(void *p)
 {
-	return t->total_alloc_size;
-}
+	off_t total = 0;
+	struct talloc_chunk *c, *tc;
 
-const char *talloc_pool_name(TALLOC_CTX const *t)
-{
-	if (t) return t->name;
+	tc = ((struct talloc_chunk *)p)-1;
 
-	return NULL;
+	total = tc->size;
+	for (c=tc->child;c;c=c->next) {
+		total += talloc_total_size(c+1);
+	}
+	return total;
 }
 
 
-/** talloc and zero memory. */
-void *talloc_zero(TALLOC_CTX *t, size_t size)
+/* 
+   talloc and zero memory. 
+*/
+void *talloc_zero(void *t, size_t size)
 {
 	void *p = talloc(t, size);
 
@@ -382,8 +295,10 @@ void *talloc_zero(TALLOC_CTX *t, size_t size)
 }
 
 
-/** memdup with a talloc. */
-void *talloc_memdup(TALLOC_CTX *t, const void *p, size_t size)
+/*
+  memdup with a talloc. 
+*/
+void *talloc_memdup(void *t, const void *p, size_t size)
 {
 	void *newp = talloc(t,size);
 
@@ -394,8 +309,10 @@ void *talloc_memdup(TALLOC_CTX *t, const void *p, size_t size)
 	return newp;
 }
 
-/** strdup with a talloc */
-char *talloc_strdup(TALLOC_CTX *t, const char *p)
+/*
+  strdup with a talloc 
+*/
+char *talloc_strdup(void *t, const char *p)
 {
 	if (!p) {
 		return NULL;
@@ -403,8 +320,10 @@ char *talloc_strdup(TALLOC_CTX *t, const char *p)
 	return talloc_memdup(t, p, strlen(p) + 1);
 }
 
-/** strndup with a talloc */
-char *talloc_strndup(TALLOC_CTX *t, const char *p, size_t n)
+/*
+  strndup with a talloc 
+*/
+char *talloc_strndup(void *t, const char *p, size_t n)
 {
 	size_t len = strnlen(p, n);
 	char *ret;
@@ -416,23 +335,7 @@ char *talloc_strndup(TALLOC_CTX *t, const char *p, size_t n)
 	return ret;
 }
 
-/**
- * Perform string formatting, and return a pointer to newly allocated
- * memory holding the result, inside a memory pool.
- **/
- char *talloc_asprintf(TALLOC_CTX *t, const char *fmt, ...)
-{
-	va_list ap;
-	char *ret;
-
-	va_start(ap, fmt);
-	ret = talloc_vasprintf(t, fmt, ap);
-	va_end(ap);
-	return ret;
-}
-
-
- char *talloc_vasprintf(TALLOC_CTX *t, const char *fmt, va_list ap)
+ char *talloc_vasprintf(void *t, const char *fmt, va_list ap)
 {	
 	int len;
 	char *ret;
@@ -452,31 +355,29 @@ char *talloc_strndup(TALLOC_CTX *t, const char *p, size_t n)
 }
 
 
-/**
- * Realloc @p s to append the formatted result of @p fmt and return @p
- * s, which may have moved.  Good for gradually accumulating output
- * into a string buffer.
- **/
- char *talloc_asprintf_append(TALLOC_CTX *t, char *s,
-			      const char *fmt, ...)
+/*
+  Perform string formatting, and return a pointer to newly allocated
+  memory holding the result, inside a memory pool.
+ */
+char *talloc_asprintf(void *t, const char *fmt, ...) _PRINTF_ATTRIBUTE(2,3)
 {
 	va_list ap;
+	char *ret;
 
 	va_start(ap, fmt);
-	s = talloc_vasprintf_append(t, s, fmt, ap);
+	ret = talloc_vasprintf(t, fmt, ap);
 	va_end(ap);
-	return s;
+	return ret;
 }
 
 
-
 /**
  * Realloc @p s to append the formatted result of @p fmt and @p ap,
  * and return @p s, which may have moved.  Good for gradually
  * accumulating output into a string buffer.
  **/
- char *talloc_vasprintf_append(TALLOC_CTX *t, char *s,
-			       const char *fmt, va_list ap)
+char *talloc_vasprintf_append(char *s,
+			      const char *fmt, va_list ap)
 {	
 	int len, s_len;
 	va_list ap2;
@@ -486,11 +387,11 @@ char *talloc_strndup(TALLOC_CTX *t, const char *p, size_t n)
 	if (s) {
 		s_len = strlen(s);
 	} else {
-		s = 0;
+		s_len = 0;
 	}
 	len = vsnprintf(NULL, 0, fmt, ap2);
 
-	s = talloc_realloc(t, s, s_len + len+1);
+	s = talloc_realloc(s, s_len + len+1);
 	if (!s) return NULL;
 
 	VA_COPY(ap2, ap);
@@ -500,109 +401,45 @@ char *talloc_strndup(TALLOC_CTX *t, const char *p, size_t n)
 	return s;
 }
 
-
-/**
- * Return a human-readable description of all talloc memory usage.
- * The result is allocated from @p t.
- **/
-char *talloc_describe_all(TALLOC_CTX *rt)
+/*
+  Realloc @p s to append the formatted result of @p fmt and return @p
+  s, which may have moved.  Good for gradually accumulating output
+  into a string buffer.
+ */
+char *talloc_asprintf_append(char *s,
+			     const char *fmt, ...) _PRINTF_ATTRIBUTE(2,3)
 {
-	int n_pools = 0, total_chunks = 0;
-	size_t total_bytes = 0;
-	TALLOC_CTX *it;
-	char *s;
-
-	if (!rt) return NULL;
-
-	s = talloc_asprintf(rt, "global talloc allocations in pid: %u\n",
-			    (uint_t) getpid());
-	s = talloc_asprintf_append(rt, s, "%-40s %8s %8s\n",
-				   "name", "chunks", "bytes");
-	s = talloc_asprintf_append(rt, s, "%-40s %8s %8s\n",
-				   "----------------------------------------",
-				   "--------",
-				   "--------");	
-	MUTEX_LOCK_BY_ID(MUTEX_TALLOC);
-	
-	for (it = list_head; it; it = it->next) {
-		size_t bytes;
-		int n_chunks;
-		fstring what;
-		
-		n_pools++;
-		
-		talloc_get_allocation(it, &bytes, &n_chunks);
-
-		if (it->name)
-			fstrcpy(what, it->name);
-		else
-			slprintf(what, sizeof(what), "@%p", it);
-		
-		s = talloc_asprintf_append(rt, s, "%-40s %8u %8u\n",
-					   what,
-					   (uint_t) n_chunks,
-					   (uint_t) bytes);
-		total_bytes += bytes;
-		total_chunks += n_chunks;
-	}
-
-	MUTEX_UNLOCK_BY_ID(MUTEX_TALLOC);
-
-	s = talloc_asprintf_append(rt, s, "%-40s %8s %8s\n",
-				   "----------------------------------------",
-				   "--------",
-				   "--------");	
-
-	s = talloc_asprintf_append(rt, s, "%-40s %8u %8u\n",
-				   "TOTAL",
-				   (uint_t) total_chunks, (uint_t) total_bytes);
+	va_list ap;
 
+	va_start(ap, fmt);
+	s = talloc_vasprintf_append(s, fmt, ap);
+	va_end(ap);
 	return s;
 }
 
-
-
-/**
- * Return an estimated memory usage for the specified pool.  This does
- * not include memory used by the underlying malloc implementation.
- **/
-void talloc_get_allocation(TALLOC_CTX *t,
-			   size_t *total_bytes,
-			   int *n_chunks)
-{
-	struct talloc_chunk *tc;
-
-	if (t) {
-		*total_bytes = 0;
-		*n_chunks = 0;
-
-		for (tc = t->list; tc; tc = tc->next) {
-			n_chunks[0]++;
-			*total_bytes += tc->size;
-		}
-	}
-}
-
 /*
-  realloc an array, checking for integer overflow in the array size
+  alloc an array, checking for integer overflow in the array size
 */
-void *talloc_realloc_array(TALLOC_CTX *ctx, void *ptr, size_t el_size, uint_t count)
+void *talloc_array(void *ctx, size_t el_size, uint_t count)
 {
 	if (count == 0 ||
 	    count >= MAX_TALLOC_SIZE/el_size) {
 		return NULL;
 	}
-	return talloc_realloc(ctx, ptr, el_size * count);
+	return talloc(ctx, el_size * count);
 }
 
 
 /*
-  we really should get rid of this
+  realloc an array, checking for integer overflow in the array size
 */
-void *talloc_strdup_w(TALLOC_CTX *mem_ctx, void *s)
+void *talloc_realloc_array(void *ptr, size_t el_size, uint_t count)
 {
-	size_t len = strlen_w(s);
-	return talloc_memdup(mem_ctx, s, (len+1)*2);
+	if (count == 0 ||
+	    count >= MAX_TALLOC_SIZE/el_size) {
+		return NULL;
+	}
+	return talloc_realloc(ptr, el_size * count);
 }
 
 /*
@@ -610,8 +447,12 @@ void *talloc_strdup_w(TALLOC_CTX *mem_ctx, void *s)
 */
 void *talloc_ldb_alloc(void *context, void *ptr, size_t size)
 {
-	return talloc_realloc((TALLOC_CTX *)context, ptr, size);
+	if (ptr == NULL) {
+		return talloc(context, size);
+	}
+	if (size == 0) {
+		talloc_free(ptr);
+		return NULL;
+	}
+	return talloc_realloc(ptr, size);
 }
-
-
-/** @} */