Arena memory allocator

Question

I'm not exactly sure if this is technically an "arena allocator" but it serves a similar purpose: providing a fast way to allocate a lot of objects that can all be freed at once.

#include <type_traits>
#include <utility>
#include <new>

template <std::size_t BlockSizeIn = 1024>
struct BlockProviderNewDelete
{
    static constexpr std::size_t BlockSize = BlockSizeIn;

    static void* allocateBlock()
    {
        return ::operator new(BlockSize);
    }
    static void freeBlock(void *block) noexcept
    {
        ::operator delete(block);
    }
};

template <class BlockProviderIn>
class ArenaAllocator
{
public:
    using BlockProvider = BlockProviderIn;

private:
    struct AllocBlock
    {
        AllocBlock *next;
        char mem[BlockProvider::BlockSize - sizeof(AllocBlock*)];
    };
    AllocBlock *base;
    AllocBlock *headBlock;
    std::size_t headIndex;

    void appendBlock()
    {
        AllocBlock *newBlock = static_cast<AllocBlock*>(BlockProvider::allocateBlock());
        newBlock->next = nullptr;
        headBlock->next = newBlock;
        headBlock = newBlock;
        headIndex = 0;
    }
    void nextBlock()
    {
        if(headBlock->next)
        {
            headBlock = headBlock->next;
            headIndex = 0;
        }
        else
            appendBlock();
    }

public:
    static constexpr std::size_t BlockSize = BlockProvider::BlockSize;
    static constexpr std::size_t MaxAllocationSize = sizeof(AllocBlock::mem);

    ArenaAllocator()
    {
        base = static_cast<AllocBlock*>(BlockProvider::allocateBlock());
        base->next = nullptr;
        headBlock = base;
        headIndex = 0;
    }
    ~ArenaAllocator()
    {
        AllocBlock *cur = base, *next;
        while(cur != nullptr)
        {
            next = cur->next;
            BlockProvider::freeBlock(cur);
            cur = next;
        }
    }

    void reset() noexcept
    {
        headBlock = base;
        headIndex = 0;
    }

    void* allocate(std::size_t s)
    {
        if(s == 0) s = 1;

        if(s > MaxAllocationSize)
            return nullptr;
        else if(s > MaxAllocationSize - headIndex)
            nextBlock();

        void *ptr = &headBlock->mem[headIndex];
        headIndex += s;
        if(headIndex >= MaxAllocationSize)
            nextBlock();

        return ptr;
    }

    template <typename T, typename... Args>
    T* construct(Args... args)
    {
        static_assert(std::is_trivially_destructible<T>::value, "Type must be trivially destructible!");
        static_assert(sizeof(T) <= MaxAllocationSize, "Type must not be larger than max allocation size!");

        T *result = static_cast<T*>(allocate(sizeof(T)));
        new (result) T(std::forward<Args>(args)...);
        return result;
    }
};

template <std::size_t BlockSize>
using ArenaAllocatorDefault = ArenaAllocator<BlockProviderNewDelete<BlockSize>>;

A caveat to this is that types allocated with the arena allocator must be trivially destructible (i.e. their memory must be reusable without destroying them first).

I'm already aware of one major issue: it doesn't consider alignment. However that's a fairly easy fix, so I'd like that to be ignored in the review. I'm mostly wondering whether this invokes any undefined behavior (other than due to ignoring memory alignment).

Here's an example of usage (this was to test if it leaked any blocks of memory or segfaulted. It didn't.):

// 2 MiB block size
ArenaAllocatorDefault<2097152> test;

for(size_t i = 0; i < 100000; ++i)
{
    for(size_t j = 0; j < 1000000; ++j)
    {
        test.construct<char[128]>();
    }
    test.reset();
}

Obviously you'd want to actually use the pointer returned by the construct() method for usual purposes but this was just for testing.

Answer 1

Missing copy constructor & assignment operator

Because you're handling raw pointers and owning memory through them, you must implement the rule of three. Otherwise you will get double deletes after some one copies your allocator.

Use of reset()

By the looks of it, this class is developed for a very specific purpose. OP hasn't told us what the purpose is unfortunately. And the class is kind of dangerous.

Calling reset() will conceptually invalidate any pointers returned by construct(...) but they will continue to be accessible and eventually overwritten with new data until the ArenaAllocator is destroyed. If some piece of code is wrongly holding a pointer to a data block after the reset this should be a bug but static and dynamic code analysis tools will likely not detect this because the pointer is still valid. Neither will you get a crash, just a quiet possibly wrong result.

Although safe if used correctly in a single threaded environment, I'm afraid that it is easy to make a mistake with this class.

Ewww! Raw new/delete

Instead of having a custom allocator policy (BlockProvider) you could use the standard std::allocator for example. By doing this you can now use std::shared_ptr with the allocator provided and get rid of the usage of raw new/delete which is bad, yet you still have the option of providing your own allocator. Don't worry, the overhead of using std::shared_ptr is minimal in this case because your blocks are large.

Overall

I don't see any obvious bugs besides the missing rule of three.

Although custom memory management has its uses, you really do want profiling data to back up the added complexity and failure points of rolling your own memory management. Unless you have a strong reason for custom management that seriously outweighs the reduction in efficacy of code analysis tools and increase in risk for bugs, I would not recommend rolling your own. You have to be sure the extra headache is worth it.

Also note, that if your type is a POD then operator delete will not call any destructors (there aren't any!). In fact I would expect various standard library functions to not call destructors on trivially destructible types any way. Apparently at least GCC does this.

If you have a piece of code that must rapidly allocate and throw away memory at a pace where the standard allocator isn't fast enough, then you might want to consider changing that code to re-use the same memory area instead. This is even faster than writing a custom allocator, solves the problem at the root and doesn't introduce near as much hair loss as custom memory management.

If you just need a lot of fixed size objects quickly and contiguously, I would consider using a fixed item size memory pool and overloaded new/delete for the class and make it transparent. You can do some very efficient reclamation and allocation when items are of fixed size.