Memory Pool and Block Alignment

Question

I have written a memory pool (pool_allocator) that was described in a book I am reading (Game Engine Architecture). The interface is pretty basic:

• The constructor: pool_allocator(std::size_t count, std::size_t block_size, std::size_t alignment);.
• void* allocate();, which returns a pointer to a memory location with (at least) the requested alignment.
• void free(void* block); which returns the block to the pool.

The general design is not complex, either. The constructor uses operator new() to allocate a chunk of memory, and that memory is treated as a linked list - any calls to allocate and free operate on the head of the list.

However, this is the first time I have ever given alignment any real consideration, and apparently if I use enough {static,reinterpret}_casts, I start to question that the Earth is round. I would be grateful for comments. My main concerns are:

• Is alignment handled properly? I think align_head() is okay, but what about minimum_alignment() and padding()?
• Are the reinterpret_cast and static_cast calls used properly, or are there better alternatives? I understand that they are necessary when handling raw data, but I am out of my comfort zone here.

If you want to go the extra mile and point out other deficiencies (which is more than welcome), keep in mind that in the current design it is not the responsibility of this object to handle error conditions or construct objects, just manage a chunk of memory.

class pool_allocator {

public:

    typedef void* pointer_type;

public:

    pool_allocator(std::size_t count, std::size_t block_size, std::size_t alignment)
        : m_data(nullptr)
        , m_head(nullptr)
        , m_blocks(count)
        , m_block_size(block_size)
        , m_padding(0)
    {
        // each block must be big enough to hold a pointer to the next
        // so that the linked list works
        if (m_block_size < sizeof(pointer_type)) {
            m_block_size = sizeof(pointer_type);
        }

        // each block must meet the alignment requirement given as well
        // as the alignment of pointer_type.
        alignment = minimum_alignment(alignof(pointer_type), alignment);

        // find the padding required for sequential blocks:
        m_padding = padding(m_block_size, alignment);

        // allocate a chunk of memory
        m_data = operator new((m_block_size + m_padding) * m_blocks + alignment);

        // align the head pointer
        align_head(alignment);

        // initialize the list
        initialize_list();
    }

    pool_allocator(pool_allocator const&) = delete;
    pool_allocator& operator=(pool_allocator const&) = delete;

    virtual ~pool_allocator()
    {
        operator delete(m_data);
    }

    // grab one free block from the pool
    pointer_type allocate()
    {
        if (m_head == nullptr) {
            return nullptr;
        }
        else {
            pointer_type result = m_head;
            m_head = *(static_cast<pointer_type*>(result));
            return result;
        }
    }

    // return the block to the pool
    void free(pointer_type block)
    {
        *(static_cast<pointer_type*>(block)) = m_head;
        m_head = block;
    }

private:

    // align_head: calculates the offset from the beginning of the 
    // allocated data chunk (m_data) to the first aligned location
    // and stores it as the void* m_head

    void align_head(std::size_t alignment)
    {
        std::uintptr_t raw_address = reinterpret_cast<std::uintptr_t>(m_data);
        std::uintptr_t c_alignment = static_cast<std::uintptr_t>(alignment);
        std::uintptr_t offset = c_alignment - (raw_address & (c_alignment - 1));

        m_head = reinterpret_cast<pointer_type>(raw_address + offset);
    }

    // initialize_list: fills the first sizeof(void*) bytes of 
    // each block in the data chunk with a pointer to the next

    void initialize_list()
    {
        std::uintptr_t current = reinterpret_cast<std::uintptr_t>(m_head);
        std::uintptr_t block_size = static_cast<std::uintptr_t>(m_block_size + m_padding);

        for (std::size_t block = 0; block < m_blocks; ++block) {
            std::uintptr_t next = current + block_size;
            *(reinterpret_cast<pointer_type*>(current)) = reinterpret_cast<pointer_type>(next);
            current = next;
        }

        // make sure the last block points nowhere
        current -= block_size;
        *(reinterpret_cast<pointer_type*>(current)) = nullptr;
    }

    // minimum_alignment: calculate the least commmon multiple of 
    // a and b and return that value

    std::size_t minimum_alignment(std::size_t a, std::size_t b)
    {
        std::size_t ta = a;
        std::size_t tb = b;

        while (tb != 0) {
            std::size_t tr = tb;
            tb = ta % tr;
            ta = tr;
        }

        return (a / ta) * b;
    }

    // padding: calculate the smallest multiple of padding that can 
    // contain block_size

    std::size_t padding(std::size_t block_size, std::size_t alignment)
    {
        std::size_t multiplier = 0;

        while (multiplier * alignment < block_size) {
            ++multiplier;
        }

        return multiplier * alignment - block_size;
    }

private:

    pointer_type m_data;
    pointer_type m_head;

    std::size_t m_blocks;
    std::size_t m_block_size;
    std::size_t m_padding;

};

Answer 1

I think you have some fundamental misunderstandings about alignment (and you can simplify your code a lot):

3.11 Alignment

3: Alignments are represented as values of the type std::size_t. Valid alignments include only those values returned by an alignof expression for the fundamental types plus an additional implementation-defined set of values, which may be empty. Every alignment value shall be a non-negative integral power of two.

So you can the alignment requirements of a type from alignof(). This value is a power of 2.

5: Alignments have an order from weaker to stronger or stricter alignments. Stricter alignments have larger alignment values. An address that satisfies an alignment requirement also satisfies any weaker valid alignment requirement.

If something satisfies the alignments for a larger alignment. Then it automatically satisfies alignment requirements for smaller values.

Thus if memory is aligned for an object of size N. Then it is also correctly aligned for objects that are smaller than 'N'.

18.6.1.1 Single-object forms [new.delete.single]

void* operator new(std::size_t size);
1: Effects: The allocation function (3.7.4.1) called by a new-expression (5.3.4) to allocate size bytes of storage suitably aligned to represent any object of that size.

Thus using new to allocate memory for a space of size 'M' means the memory returned will also be aligned for objects of size 'M'. This also means that it aligned for all objects that are smaller than 'M'. Thus for your block of memory that will hold multiple objects of type 'N' such that `M = Count*alignof(N)' it is automatically aligned for all objects of type 'N'.