Arena Memory Allocator

Background

• An arena is a memory allocator which sometimes can replace malloc/free. It's main advantages are that it is very fast compared with malloc and it does not require deallocation of individual objects. In fact, it is not possible to deallocate individual objects. Compared with malloc, arenas do not introduce any memory overhead except for alignment (malloc requires some extra space so that free can know what to do with the data).
• An arena abstract data type has at least three functions:
  • a constructor, eg arena_t* new_arena(void),
  • a destructor, eg void free_arena(arena_t* arena) and
  • an allocator, eg void* alloc(arena_t* arena, size_t size, size_t align).
• size_t is an implementation-defined unsigned integer type found eg in stddef.h.
• To describe an arena, we first consider a simplified version and then correct it. The simplified version consists of a struct (allocated with malloc) which contains at least the following
  • a large char array with eg 4096 elements, and
  • a pointer into this char array.
• Memory is allocated from the array.
• The pointer points to the next address to allocate. When size bytes are allocated, the current value of the pointer should be returned to the user (ie the caller of alloc()) and the pointer is incremented by size.
• When the user no longer needs any object allocated from this arena, then the arena can be deallocated, which typically will call free (or will put the arena on a free-list of unused arena structs).
• The first problem with the above simplified arena is alignment (see Section 6.1.3, page 184 in the course book for an introduction to alignment). Suppose the beginning of the array is aligned on 8 bytes, and a double has an alignment requirement of 8 bytes. Then it is safe to first allocate memory for a double from the arena (since the pointer was at an address which is a multiple of 8 bytes), but if the next allocation request is only one byte, and the third is another 8 bytes for a double, then the double will not be allocated an address which is a multiple of 8 bytes. The arena could of course make a conservative guess that if the size is A bytes then the returned address should be a multiple of A bytes, but that is a memory waste since eg 8 bytes might be needed for a string, which has no alignment requirement, or for two ints which might have an alignment requirement of 4 bytes. The solution is simply to use a parameter which says explicitly what alignment requirement the allocation request has.
• The second problem is more obvious: the array in the arena might be too small. A solution is to make the arena a list of such structs, and thus never let the user notice that the array does not have enough memory left, but rather simply allocate another such struct and somehow link it with the previously allocated structs. The destructor should deallocate all the structs on such a list.

Tasks

1. The first task in Assignment 3 is to implement an arena, and to write a simple test program to check that it works.
   
   
2. The second task is to change your program from Assignment 1 to use your arena when possible. If you have a function which creates an object with memory allocated from malloc/calloc, you can add a similar function which has one more parameter, a pointer to an arena, and allocates the memory from the arena instead. Change you program's deallocation functions accordingly.
   
   
3. Then compare the execution times of the program from A1 and the new program.
   
   
4. Summarise in one sentence in a comment in your arena implementation when you can use an arena instead of malloc/free.