10
\$\begingroup\$

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;
\$\endgroup\$
  • 1
    \$\begingroup\$ Detecting buffer overflows with canary terminator. I would separate this out into a second allocator. So you have a basic allocator. Then a debug allocator that extends your basic allocator with canary objects around the allocated space. \$\endgroup\$ – Martin York Apr 20 '16 at 23:25
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ And it may be valuable to add move ctor/assignment operator. \$\endgroup\$ – cloakedlearning Jul 17 '16 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.