halloc

Hierarchical memory allocator for C

Hierarchical allocator (halloc) is an extension to a standard malloc/free interface that simplifies memory deallocation tasks in cases when allocated structures exhibit hierarchical properties.

In short

Memory blocks allocated through halloc can be optionally organized into a hierarchy of parent-child relationships. These relationships are taken into an account when a block is being freed -- disposing the block automatically frees all its children in recursive fashion. For example:

struct foo * p = h_malloc(sizeof(*p));
struct bar * q = h_calloc(sizeof(*q), 10);
struct tmp * r = h_calloc(sizeof(*r), 20);

hattach(q, p);  /* q is now a child of p */
hattach(r, q);  /* r is now a child of q and a grandchild of p */

h_free(p);

The h_free call disposes not just the p block, but the q and r blocks as well.

Download

Halloc is an open source project released under the BSD license and hosted on GitHub: halloc on github The code is light, fast and portable. The latest version is 1.2.1, released May 2010.

Interface

Core API consists of exactly two functions:

void * halloc(void * ptr, size_t len);

which is functionally identical to the standard realloc() and

void hattach(void * block, void * parent);

which assigns parent to be a parent of the block. If parent is NULL, the block is detached from its current parent if there is one.

There is also a malloc-style API that can be used as a drop-in replacement for standard malloc/free calls:

void * h_malloc(size_t len)
void * h_calloc(size_t n, size_t len);
void * h_realloc(void * ptr, size_t len);
void   h_free(void * ptr);
char * h_strdup(const char * str);

See halloc.h for details.

Intended use

Simplified dynamic structure management

Many dynamically allocated structures are inherintely hierarchical with one master structure referring to a number of subordinate ones, which in turn may have their own dependendants.

A good example is a datamodel of a typical network server application, which maintains a separate session context for every active client. As the session goes through various states, the context gets populated with different dynamic data, which in turn may be comprised of multiple dynamic heap objects. Tearing down the session usually involves cascading free() calls to dispose all allocated data.

Using halloc in this case would allow associating all session data with a central session object and then disposing them all with h_free(session).

Memory pooling and garbage collection

Memory pooling is frequently used to provide parts of the code with their own memory manipulation context. The context is used to track all memory allocations and allows disposing all "outstanding" (or leaked) blocks after the code has completed its execution.

Memory pooling is essentially a simple garbage collection mechanism. It is especially useful in (yet another type of) server applications, where every client request is associated with its own memory pool and the server code does not bother freeing individual memory blocks it may temporarily use while processing the request.

For example, Apache Web Server uses pools to manage memory, file descriptors and even the processes.

Here's a simple halloc-based memory pool API:

typedef int pool_t;

pool_t * pool_create()
{
	return h_malloc(sizeof(pool_t));
}

void pool_destroy(pool_t * p)
{
	h_free(p, 0);
}

void * pool_alloc(size_t len, pool_t * pool)
{
	void * ptr = h_malloc(len);
	if (! ptr)
		return 0;
	hattach(ptr, pool);
	return ptr;
}

void pool_free(void * ptr)
{
	h_free(ptr);
}

Advanced integration with halloc

realloc_t

If you haven't looked at the realloc recently, here is a quick recap.

The primary realloc() usage is to reallocate (to grow or to shrink) memory blocks previously obtained through malloc() or calloc() calls. However realloc can also be used to allocate new and dispose existing blocks. Specifically,

realloc(NULL, n) is equivalent to malloc(n)
realloc(   p, 0) is equivalent to free(p)

This versatility makes it a remarkable function in a sense that it can provide a single-point access to all core memory heap operations.

Custom allocator

Halloc is essentialy a proxy between the application using its API and an underlying memory heap manager, which is used for actual heap manipulation. This is where realloc comes into the picture -- the halloc interacts with the memory manager through a single realloc-typed function pointer -

realloc_t halloc_allocator;

The pointer is declared in halloc.h and defaults to the standard realloc(). Repointing halloc_allocator to a custom function allows hooking all heap operations requested by halloc. For example -

void * my_alloc(void * ptr, size_t len)
{
	printf("%p %d\n", ptr, len);
	return realloc(ptr, len);
}

int main(int argc, char ** argv)
{
	halloc_allocator = my_alloc;
	...
}