Block allocator

Question

I wrote this block allocator for exercise and would love to get your reviews.

Main features I wanted to have:

• Detecting buffer overflows with canary terminator.
• Being able to allocate arbitrary types with template allocator and allow types that may fit more than one blocks (continues chunks).

#include <cstdlib>
#include <cstdint>
#include <cstddef>
#include <new>
#include <exception>

class BadAddressException: public std::exception
{
public:
    const char* what() const noexcept override
    {
        return "None-owned or incorrect pointer.";
    }
};

class BufferOverflowException: public std::exception
{
public:
    const char* what() const noexcept override
    {
        return "Buffer overflow detected.";
    }
};

class BlockAllocator
{

public:

    BlockAllocator( size_t blockSize, size_t maxBlocks, size_t blockAlignment )
        :maxBlocks( maxBlocks )
        ,newBlockAlignment( SYSTEM_ALIGNMENT > blockAlignment ? SYSTEM_ALIGNMENT : blockAlignment )
        ,alignedBlockSize( roundUpTo( blockSize, blockAlignment ) )
        ,maxChunks( divideRoundUp<size_t>( maxBlocks, 2 ) )
        ,availableBlocks( maxBlocks )
        ,chunkIndex( 0 )
        ,buffer( nullptr )
        ,controls( nullptr )
    {

        if ( !isValidAlignmentValue( blockAlignment ) )
        {
            throw std::bad_alloc{};
        }

        const size_t blocksPadding      = padding( SYSTEM_ALIGNMENT, newBlockAlignment );
        const size_t controlsPadding    = padding( SYSTEM_ALIGNMENT, alignof( Control ) );
        const size_t chunksPadding      = padding( SYSTEM_ALIGNMENT, alignof( Chunk ) );

        const size_t allocationSize     =   blocksPadding + alignedBlockSize * maxBlocks +
                                            CANARY_TERMINATOR_SIZE +
                                            controlsPadding + maxBlocks * sizeof( Control ) +
                                            chunksPadding + maxChunks * sizeof( Chunk );

        buffer                          = malloc( allocationSize );

        if( buffer == nullptr )
        {
            throw std::bad_alloc{};
        }

        const uintptr_t blocksStart     = ptrToInt( buffer );
        const uintptr_t canaryStart     = blocksStart + maxBlocks * alignedBlockSize;
        const uintptr_t controlsStart   = roundUpTo( canaryStart + CANARY_TERMINATOR_SIZE, alignof( Control ) );
        const uintptr_t chunksStart     = roundUpTo( controlsStart + maxBlocks * sizeof( Control ), alignof( Chunk ) );

        controls                        = reinterpret_cast<Control*>( intToPtr( controlsStart ) );
        canary                          = reinterpret_cast<char*>( intToPtr( canaryStart ) );
        chunks                          = reinterpret_cast<Chunk*>( intToPtr( chunksStart ) );

        for( size_t index = 0; index < CANARY_TERMINATOR_SIZE; ++index )
        {
            canary[ index ]                     = 0;
        }

        for( size_t index = 0; index < maxBlocks; ++index )
        {
            controls[ index ].used              = false;
            controls[ index ].owner             = 0;
            controls[ index ].typeAlignedPtr    = nullptr;
        }

        for( size_t index = 0; index < maxChunks; ++index )
        {
            chunks[ index ].index               = 0;
            chunks[ index ].size                = 0;
            chunks[ index ].next                = nullptr;
        }
    }

    ~BlockAllocator()
    {
        free( buffer );
    }

    template<typename TypeT, typename ... ArgsT>
    TypeT * Allocate( const ArgsT & ... args )
    {
        if( maxBlocks == 0 || alignedBlockSize == 0 )
        {
            return nullptr;
        }

        if( !checkCanaryTerminator() )
        {
            throw BufferOverflowException{};
        }

        const size_t objectPadding      = padding( newBlockAlignment, alignof( TypeT ) );
        const size_t totalObjectSize    = objectPadding + sizeof( TypeT );
        const size_t requestBlockSize   = divideRoundUp( totalObjectSize, alignedBlockSize );

        if( availableBlocks < requestBlockSize )
        {
            return nullptr;
        }

        const BlockAllocResult allocBlockResult = allocateBlocks( requestBlockSize );

        if( allocBlockResult.success )
        {
            const uintptr_t blockAddress    = roundUpTo( ptrToInt( buffer ), newBlockAlignment ) + alignedBlockSize * allocBlockResult.index;
            const uintptr_t objectAddress   = roundUpTo( blockAddress, alignof( TypeT ) );

            void* placement                 = intToPtr( objectAddress );
            TypeT* result                   = nullptr;

            try {

                result                      = new( placement ) TypeT( args... );

            } catch ( ... ) {

                result                      = nullptr;
                freeBlocksAt( allocBlockResult.index );

                throw;
            }

            Control & control               = controls[ allocBlockResult.index ];
            control.typeAlignedPtr          = placement;

            availableBlocks                 -= requestBlockSize;

            return result;
        }

        return nullptr;
    }

    void* Allocate()
    {
        if( !checkCanaryTerminator() )
        {
            throw BufferOverflowException{};
        }

        if( availableBlocks == 0 )
        {
            return nullptr;
        }

        const BlockAllocResult allocBlockResult = allocateBlocks( 1 );

        if( allocBlockResult.success )
        {
            availableBlocks--;

            return intToPtr( roundUpTo( ptrToInt( buffer ), newBlockAlignment ) + alignedBlockSize * allocBlockResult.index );
        }

        return nullptr;
    }

    template<typename TypeT>
    void Free( TypeT * p )
    {
        if( p == nullptr )
        {
            return;
        }

        if( maxBlocks == 0 || alignedBlockSize == 0 )
        {
            throw BadAddressException{};
        }

        if( ptrToInt( p ) < roundUpTo( ptrToInt( buffer ), newBlockAlignment ) ||
            ptrToInt( p ) > roundUpTo( ptrToInt( buffer ), newBlockAlignment ) + ( maxBlocks - 1 ) * alignedBlockSize )
        {
            throw BadAddressException{};
        }

        if( !checkCanaryTerminator() )
        {
            throw BufferOverflowException{};
        }

        const size_t objectPadding          = padding( newBlockAlignment, alignof( TypeT ) );
        const size_t totalObjectSize        = objectPadding + sizeof( TypeT );
        const size_t requestBlockSize       = divideRoundUp( totalObjectSize, alignedBlockSize );

        const uintptr_t blockAddress        = ptrToInt( p ) - ( ptrToInt( p ) % newBlockAlignment );

        const size_t blockIndex             = ( blockAddress - roundUpTo( ptrToInt( buffer ), newBlockAlignment ) ) / alignedBlockSize;
        const size_t ownerBlockIndex        = controls[ blockIndex ].owner;

        if( controls[ ownerBlockIndex ].typeAlignedPtr != static_cast<void*>( p ) )
        {
            throw BadAddressException{};
        }

        if( freeBlocksAt( ownerBlockIndex ) )
        {
            availableBlocks                 -= requestBlockSize;

            p->~TypeT();
        } else {
            throw BadAddressException{};
        }
    }

    void Free( void* p )
    {
        if( p == nullptr )
        {
            return;
        }

        if( maxBlocks == 0 || alignedBlockSize == 0 )
        {
            throw BadAddressException{};
        }

        if (    ptrToInt( p ) < roundUpTo( ptrToInt( buffer ), newBlockAlignment ) ||
                ptrToInt( p ) > roundUpTo( ptrToInt( buffer ), newBlockAlignment ) + ( maxBlocks - 1 ) * alignedBlockSize ||
                !isAlignedTo( ptrToInt( p ), newBlockAlignment ) )
        {
            throw BadAddressException{};
        }

        if( !checkCanaryTerminator() )
        {
            throw BufferOverflowException{};
        }

        if( !freeBlocksAt( ( ptrToInt( p ) - roundUpTo( ptrToInt( buffer ), newBlockAlignment ) ) / alignedBlockSize ) )
        {
            throw BadAddressException{};
        }

        availableBlocks++;
    }

private:

    static const size_t SYSTEM_ALIGNMENT        = alignof( max_align_t );
    static const size_t CANARY_TERMINATOR_SIZE  = SYSTEM_ALIGNMENT;

    struct BlockAllocResult
    {
        bool    success;
        size_t  index;
    };

    struct Control
    {
        bool    used;
        size_t  owner;
        void*   typeAlignedPtr;
    };

    struct Chunk
    {
        size_t  index;
        size_t  size;

        Chunk*  next;
    };

private:


    template<typename T>
    inline T padding( T originalAlignment, T newAlignment )
    {
        return ( originalAlignment > newAlignment ? originalAlignment : newAlignment ) - originalAlignment;
    }

    template<typename T>
    inline T roundUpTo( T value, T alignment ) const
    {
        return ( value + alignment - 1 ) & ~( alignment - 1 );
    }

    template<typename T>
    inline T divideRoundUp( T value, T divider )
    {
        if( value == 0 )
        {
            return 0;
        }

        return 1 + ( ( value - 1 ) / divider );
    }

    inline uintptr_t ptrToInt( void * value ) const
    {
        return reinterpret_cast<uintptr_t>( value );
    }

    inline void * intToPtr( uintptr_t value ) const
    {
        return reinterpret_cast<void*>( value );
    }

    inline bool isValidAlignmentValue( size_t value  ) const
    {
        return ( value > 0 ) && ( ( value & ( value - 1 ) ) == 0 );
    }

    inline bool isAlignedTo( uintptr_t value, uintptr_t alignment ) const
    {
        return ( value & ( alignment - 1 ) ) == 0;
    }

    bool checkCanaryTerminator()
    {
        for( size_t index = 0; index < CANARY_TERMINATOR_SIZE; ++index )
        {
            if( canary[ index ] != 0 )
            {
                return false;
            }
        }

        return true;
    }

    bool freeBlocksAt( size_t index )
    {
        if( index < maxBlocks &&
            controls[ index ].owner == index &&
            controls[ index ].used )
        {
            controls[ index ].used      = false;

            if( index > 0 &&
                !controls[ index - 1 ].used )
            {
                controls[ index ].owner = controls[ index - 1 ].owner;
            }

            size_t it   = index + 1;

            while ( it < maxBlocks &&
                    ( !controls[ it ].used || ( controls[ it ].used && controls[ it ].owner == index ) ) )
            {
                controls[ it ].used     = false;
                controls[ it ].owner    = controls[ index ].owner;

                it++;
            }

            return true;
        }

        return false;
    }

    BlockAllocResult allocateBlocks( size_t requestedSize )
    {
        Chunk* chunksBiggerEnough   = getChunksLargerOrEqualTo( requestedSize );
        Chunk* bestMatch            = getSmallestChunk( chunksBiggerEnough );

        if ( bestMatch != nullptr )
        {
            for (   size_t index = bestMatch->index;
                    index < bestMatch->index + bestMatch->size;
                    ++index )
            {
                if( index < bestMatch->index + requestedSize )
                {
                    controls[ index ].owner = bestMatch->index;
                    controls[ index ].used  = true;
                } else {
                    controls[ index ].owner = bestMatch->index + requestedSize;
                }
            }

            return BlockAllocResult{ true, bestMatch->index };
        }

        return BlockAllocResult{ false, 0 };
    }

    Chunk * nextChunk( size_t index, size_t size, Chunk * next )
    {
        Chunk * result  = &chunks[ chunkIndex ];

        result->index   = index;
        result->size    = size;
        result->next    = next;

        chunkIndex      = ( chunkIndex + 1 ) % maxChunks;

        return result;
    }

    Chunk* getChunksLargerOrEqualTo( size_t requestedSize )
    {
        Chunk* current  = nullptr;
        Chunk* root     = nullptr;
        Chunk* tail     = nullptr;

        for( size_t index = 0; index < maxBlocks; ++index )
        {
            if( !controls[ index ].used )
            {
                if( current == nullptr )
                {
                    current = nextChunk( index, 1, nullptr );
                } else {
                    current->size++;
                }
            } else {

                if(  current != nullptr )
                {
                    if( current->size == requestedSize )
                    {
                        root    = current;
                        tail    = root;
                        current = nullptr;

                        break;
                    } else if( current->size > requestedSize ) {
                        if( root == nullptr )
                        {
                            root        = current;
                            tail        = root;
                        } else {
                            tail->next  = current;
                            tail        = tail->next;
                        }

                        current = nullptr;
                    }
                }
            }
        }

        if(  current != nullptr )
        {
            if( current->size == requestedSize )
            {
                root            = current;
            } else if( current->size > requestedSize ) {
                if( root == nullptr )
                {
                    root        = current;
                } else {
                    tail->next  = current;
                    tail        = tail->next;
                }
            }
        }

        return root;
    }

    Chunk* getSmallestChunk( Chunk * chunk )
    {
        if( chunk != nullptr )
        {
            Chunk* smallest     = chunk;
            Chunk* it           = smallest->next;

            while ( it != nullptr )
            {
                if( it->size < smallest->size )
                {
                    smallest    = it;
                }

                it  = it->next;
            }

            return smallest;
        }

        return nullptr;
    }

private:

    const size_t    maxBlocks;
    const size_t    newBlockAlignment;
    const size_t    alignedBlockSize;
    const size_t    maxChunks;

    size_t          availableBlocks;
    size_t          chunkIndex;

    void*           buffer;
    char*           canary;
    Control*        controls;
    Chunk*          chunks;
};

const size_t BlockAllocator::SYSTEM_ALIGNMENT;
const size_t BlockAllocator::CANARY_TERMINATOR_SIZE;

Answer 1

If I am not mistaken copy constructor and assignment operator are going to be generated for BlockAllocator class by compiler. You probably don't want the default implementation because of buffer pointer.