Arenas

Consider the following memory allocation pattern:

This group of objects can be optimized by using arena allocation.

An arena is a block (or blocks) of memory from which we allocate objects as needed. Once the objects are no longer needed, the block (or blocks) of memory for that arena are released.

There are several variations of arenas possible:

The API shown below is for multiple, heterogeneous, arenas


	#include "arena_xmemory-private.h"

	typedef struct arena_xmemory * arena_xmemory;

	arena_xmemory * init_arena_xmemory(void);
	void free_arena_xmemory(arena_xmemory);


	#define xalloc_arena(_arena, _type) \
		((_type*)do_alloc_arena_xmemory(_arena, sizeof(_type)))
	#define xalloc_arena(_arena, _type, _n) \
		((_type*)do_alloc_arena_xmemory(_arena, sizeof(_type)*(_n)))

The private header for the arena is as follows:


	/* in arena_xmemory-private.h */
	/* pick the CUTOFF_ARENA_XMEMORY so that objects to be allocated
	 * are, in general, considerably smaller than this value.
	 */
	#define BYTES_ARENA_XMEMORY	(1<<16)
	#define CUTOFF_ARENA_XMEMORY	(1<<15)

	/* worst case alignment of objects */
	#define ALIGN_ARENA_XMEMORY	8

	struct arena_xmemory {
	  struct arena_xmemory *	ax_next;
	  char *			ax_data;
	  char *			ax_at;
	  int				ax_size;
	};
	/* along with the usual accessors */

	void * do_alloc_arena_xmemory(arena_xmemory, size_t bytes);

The implementation for the arena is as follows:


	/* in arena_xmemory.c */
	arena_memory
	init_arena_xmemory( void )
	{
	  arena_xmemory	arena = xalloc(struct arena_xmemory);
	  char *	data = xnalloc(char, BYTES_ARENA_XMEMORY);

	  /* add code to handle NULL data or arena */
	  x_next_arena_xmemory(arena) = 0;
	  x_data_arena_xmemory(arena) = data;
	  x_at_arena_xmemory(arena) = data+BYTES_ARENA_XMEMORY;
	  x_size_arena_xmemory(arena) = BYTES_ARENA_XMEMORY;
	  return arena;
	}

	void *
	do_alloc_arena_xmemory(
		arena_xmemory *	arena,
		size_t		bytes
		)
	{
	  char *		data = data_arena_xmemory(arena);
	  char *		at = at_arena_xmemory(arena);
	  arena_xmemory		arena2;
	  unsigned		rem;

	  rem = bytes%ALIGN_ARENA_XMEMORY;
	  bytes = (rem==0)?bytes:(bytes+ALIGN_ARENA_XMEMORY-rem);

	  if( at - data < bytes ) {

	    if( bytes >= CUTOFF_ARENA_MEMORY ) {
	      /* handle case for large chunks; useless
	       * if this will never happen
	       */
	      arena2 = xalloc(struct arena_xmemory);
	      data = xnalloc(char, bytes);
	      x_next_arena_xmemory(arena2) = x_next_arena_xmemory(arena);
	      x_data_arena_xmemory(arena2) = data;
	      x_size_arena_xmemory(arena2) = bytes;

	      x_next_arena_xmemory(arena) = arena2;
	      return data2;
	    }

	    arena2 = xalloc(struct arena_xmemory);
	    *arena2 = *arena;
	    x_next_arena_xmemory(arena) = arena2;

	    data = xnalloc(char, BYTES_ARENA_MEMORY);
	    x_data_arena_xmemory(arena) = data;
	    x_at_arena_xmemory(arena) = data+BYTES_ARENA_XMEMORY;
	    x_size_arena_xmemory(arena) = BYTES_ARENA_XMEMORY;
	  }

	  x_at_arena_xmemory(arena) -= bytes;
	  return at_arena_xmemory(arena);
	}

	void
	free_arena_xmemory(
		arena_xmemory *	arena
		)
	{
	  arena_xmemory *	next;

	  for( ; arena; arena = next ) {
	    next = next_arena_xmemory(arena);
	    xnfree(char, size_arena_xmemory(arena), data_arena_xmemory(arena));
	    xfree(struct arena, arena);
	  }
	}

Note that we have spent some effort trying to make sure that the arena will handle requests of arbitrary sizes. However, in general, we should pick objects to be arena allocated so that their size is considerably smaller than the arena.

The allocation routines of objects have to be modified to support arenas. For example:


	T *
	make_T(
		arena_xmemory	arena,
		/*...*/
		)
	{
	  T *	newT;

	  if( arena ) {
	    newT = xalloc_arena(arena, T);
	  }
	  else {
	    newT = xalloc(T);
	  }
	  /* ... */
	  return newT;
	}


When I use arena based allocation, I often convert the common case of allocation into a macro:


	/* in arena_xmemory-private.h */
	#define align_size_arena_xmemory(_s) \
		((((_s)%ALIGN_ARENA_XMEMORY)==0)?(_s):\
		  ((_s)+ALIGN_ARENA_XMEMORY-((_s)%ALIGN_ARENA_XMEMORY)))

	#define fast_xalloc_arena(_arena, _type) \
		( align_size_arena_xmemory(sizeof(_type)) > \
		      (at_arena_xmemory(_arena)-data_arena_xmemory(_arena)) ? \ 
		  ((_type *) do_alloc_arena(_arena, sizeof(_type))): \
		  ((_type *) (x_at_arena_xmemory(_arena) -= \
		      align_size_arena_xmemory(sizeof(_type))) ) )

      /* in arena_xmemory.h */
      #define xalloc_arena(_arena, _type) \
      		fast_xalloc_arena(_arena, _type)

The complicated expression align_size_arena_xmemory() has all constant inputs, and ends up evaluating to a constant at compile time. Consequently, the common case of arena allocation, i.e. allocating one object of some type without needing a new block of memory, ends up taking only a few instructions.


Next Prev Main Top Feedback