C++: Arena Storage Pool

Bjarne-stroustrup
 

Dynamically allocated objects take their memory from a heap. The memory for an object is provided by an allocator which maintains the storage pool used for the heap. Often a call to allocator is denoted as

P := new T

where T is the type of an allocated object and P is a reference to the object.

The storage pool chosen by the allocator can be determined by either:

  • the object type T;
  • the type of pointer P.

In the former case objects can be allocated only in one storage pool. In the latter case objects of the type can be allocated in any storage pool or on the stack.

Task description
The task is to show how allocators and user-defined storage pools are supported by the language. In particular:

  1. define an arena storage pool. An arena is a pool in which objects are allocated individually, but freed by groups.
  2. allocate some objects (e.g., integers) in the pool.

Explain what controls the storage pool choice in the language.

In C++, the situation with allocators is quite complex:

  • You can define class-specific allocation/deallocation by adding class members operator new and operator delete. Those are then used whenever you use new for that type (or a type derived from it, if it doesn’t itself replace operator new), and when you delete an object of that type. Note that arrays and single objects have both separate allocation functions and deallocation functions.
  • You can replace the global allocation/deallocation routines, which are used by new/delete whenever there are no class specific functions available.
  • You can write operator new/operator delete with additional arguments, both in a class and globally. To use those, you add those parameters after the keyword new, like
T* foo = new(arena) T;
  • In addition, for objects in containers, there’s a completely separate allocator interface, where the containers use an allocator object for allocating/deallocating memory.

The following code uses class-specific allocation and deallocation functions:

#include <csttdlib>
#include <cassert>
#include <new>

// This class basically provides a global stack of pools; it is not thread-safe, and pools must be destructed in reverse order of construction
// (you definitely want something better in production use :-))
class Pool
{
public:
	Pool(std::size_type sz);
	~Pool();
	static Pool& current() { return *cur; }
	void* allocate(std::size_type sz, std::size_t alignment);
private:
	char* memory; // char* instead of void* enables pointer arithmetic
	char* free;
	char* end;
	Pool* prev;
	static Pool* cur;

	// prohibit copying
	Pool(Pool const&); // not implemented
	Pool& operator=(Pool const&); // not implemented
};

Pool* pool::cur = 0;

Pool::Pool(std::size_type size):
memory(static_cast<char*>(::operator new(size))),
free(memory),
end(memory))
{
	prev = cur;
	cur = this;
}

Pool::~Pool()
{
	::operator delete(memory);
	cur = prev;
}

void* Pool::allocate(std::size_t size, std::size_t alignment)
{
	char* start = free;

	// align the pointer
	std::size_t extra = (start - memory) % aligment;
	if (extra != 0)
	{
		extra = alignment - extra;
	}

	// test if we can still allocate that much memory
	if (end - free < size + extra)
	throw std::bad_alloc();

	// the free memory now starts after the newly allocated object
	free = start + size + extra;
	return start;
}

// this is just a simple C-like struct, except that it uses a specific allocation/deallocation function.
struct X
{
	int member;
	void* operator new(std::size_t);
	void operator delete(void*) {} // don't deallocate memory for single objects
};

void* X::operator new(std::size_t size)
{
	// unfortunately C++ doesn't offer a portable way to find out alignment
	// however, using the size as alignment is always safe (although usually wasteful)
	return Pool::current().allocate(size, size);
}

// Example program
int main()
{
	Pool my_pool(3*sizeof(X));
	X* p1 = new X; // uses the allocator function defined above
	X* p2 = new X;
	X* p3 = new X;
	delete p3; // doesn't really deallocate the memory because operator delete has an empty body

	try
	{
		X* p4 = new X; // should fail
		assert(false);
	}
	catch(...)
	{
	}

	X* p5 = new X[10]; // uses global array allocation routine because we didn't provide operator new[] and operator delete[]
	delete[] p5; // global array deallocation

	Pool* my_second_pool(1000); // a large pool
	X* p6 = new X; // allocate a new object from that pool
	X* p7 = new X;
	delete my_second_pool // also deallocates the memory for p6 and p7

} // Here my_pool goes out of scope, deallocating the memory for p1, p2 and p3

SOURCE

Content is available under GNU Free Documentation License 1.2.