/**
* @file lib.Heap.hpp
* @author Sergey Baigudin, sergey@baigudin.software
* @copyright 2014-2022, Sergey Baigudin, Baigudin Software
*/
#ifndef LIB_HEAP_HPP_
#define LIB_HEAP_HPP_
#include "api.Heap.hpp"
#include "lib.MutexGuard.hpp"
namespace eoos
{
namespace lib
{
/**
* @class Heap
* @brief Heap memory.
*
* Hardware address for system heap memory has to be aligned to eight.
*/
class Heap : public api::Heap
{
typedef Heap Self;
class NoAllocator;
public:
/**
* @brief Constructor.
*
* @param size Total heap size.
* @param mutex A mutex to protect memory allocation.
*/
Heap(size_t size, api::Mutex& mutex)
: api::Heap()
, data_(size, mutex)
, temp_() {
bool_t const isConstructed( construct() );
setConstructed( isConstructed );
}
/**
* @brief Destructor.
*/
virtual ~Heap() ///< UT Justified Branch: Language dependency
{
data_.key = 0;
}
/**
* @copydoc eoos::api::Object::isConstructed()
*/
virtual bool_t isConstructed() const
{
if( data_.key != HEAP_KEY )
{ ///< UT Justified Branch: HW dependency
return false;
}
if( !getFirstHeapBlock()->isConstructed() )
{ ///< UT Justified Branch: HW dependency
return false;
}
return true;
}
/**
* @copydoc eoos::api::Heap::allocate(size_t,void*)
*/
virtual void* allocate(size_t const size, void* ptr)
{
if( !isConstructed() )
{
return NULLPTR;
}
if( ptr == NULLPTR )
{
MutexGuard<NoAllocator> guard( *data_.mutex );
ptr = getFirstHeapBlock()->alloc(size);
}
return ptr;
}
/**
* @copydoc eoos::api::Heap::free(void*)
*/
virtual void free(void* ptr)
{
if( !isConstructed() )
{
return;
}
if( ptr == NULLPTR )
{
return;
}
MutexGuard<NoAllocator> guard( *data_.mutex );
getHeapBlock(ptr)->free();
}
/**
* @brief Operator new.
*
* Function initiates a building of heap memory
* checks and tests self memory structure data
* and leads to call the class constructor.
*
* @param size Unused.
* @param ptr Aligned to eight memory address.
* @return Address of memory or NULLPTR.
*/
static void* operator new(size_t, uintptr_t const ptr) EOOS_KEYWORD_NOEXCEPT
{
void* memory;
void* address( reinterpret_cast< void* >(ptr) ); ///< SCA MISRA-C++:2008 Justified Rule 5-2-8
if(address == NULLPTR)
{
// No class constructor call
memory = address;
}
else
{
// Create the heap
memory = create(address);
}
return memory;
}
/**
* @brief Operator delete.
*/
static void operator delete(void*, uintptr_t) {} ///< UT Justified Branch: Language dependency
/**
* @brief Operator delete.
*/
static void operator delete(void*) {} ///< UT Justified Branch: Language dependency
private:
class HeapBlock;
/**
* @copydoc eoos::lib::Object::setConstructed(bool_t)
*/
void setConstructed(bool_t const flag)
{
if(data_.key == HEAP_KEY)
{
data_.key = flag ? HEAP_KEY : 0;
}
}
/**
* @brief Constructor.
*
* @return True if object has been constructed successfully.
*/
bool_t construct()
{
// Crop a size to multiple of eight
if( (sizeof(HeapBlock) + 16UL) > data_.size )
{ ///< UT Justified Branch: HW dependency
return false;
}
// Test Heap and HeapBlock structures sizes witch has to be multipled to eight
if( (sizeof(Heap) & 0x7UL) != 0UL )
{ ///< UT Justified Branch: HW dependency
return false;
}
if( (sizeof(HeapBlock) & 0x7UL) != 0UL )
{ ///< UT Justified Branch: HW dependency
return false;
}
// Test memory
uintptr_t const addr( reinterpret_cast<uintptr_t>(this) + sizeof(Heap) ); ///< SCA MISRA-C++:2008 Justified Rule 5-2-9
void* ptr ( reinterpret_cast<void*>(addr) ); ///< SCA MISRA-C++:2008 Justified Rule 5-2-8
if( !isMemoryAvailable(ptr, data_.size) )
{ ///< UT Justified Branch: HW dependency
return false;
}
// Alloc first heap block
data_.block = new ( getFirstHeapBlock() ) HeapBlock(this, data_.size);
return (data_.block != NULLPTR) ? true : false;
}
/**
* @brief Returns a first heap block address.
*
* @return Pointer to heap block.
*/
HeapBlock* getFirstHeapBlock() const
{
uintptr_t const addr( reinterpret_cast<uintptr_t>(this) + sizeof(Heap) ); ///< SCA MISRA-C++:2008 Justified Rule 5-2-9
return reinterpret_cast<HeapBlock*>(addr); ///< SCA MISRA-C++:2008 Justified Rule 5-2-8
}
/**
* @brief Returns a heap block by user data address.
*
* @return Pointer to heap block.
*/
static HeapBlock* getHeapBlock(void* const data)
{
uintptr_t const addr( reinterpret_cast<uintptr_t>(data) - sizeof(HeapBlock) ); ///< SCA MISRA-C++:2008 Justified Rule 5-2-9
return reinterpret_cast<HeapBlock*>(addr); ///< SCA MISRA-C++:2008 Justified Rule 5-2-8
}
/**
* @brief Allocates memory for heap.
*
* Function initiates a building of heap memory
* checks and tests self memory structure data
* and leads to call the class constructor.
*
* @param ptr Aligned to eight memory address.
* @return Address of memory or NULLPTR.
*/
static void* create(void* ptr)
{
// Size of this class has to be multipled to eight
if( (sizeof(Heap) & 0x7UL) != 0UL )
{ ///< UT Justified Branch: HW dependency
ptr = NULLPTR;
}
// Testing memory for self structure data
//
// @todo copy constructor of the Heap class for
// temporary copying the tested memory to that
// class. This way would help to restore original
// memory data if the test were failed.
if( !isMemoryAvailable(ptr, sizeof(Heap)) )
{ ///< UT Justified Branch: HW dependency
ptr = NULLPTR;
}
// Memory address has to be aligned to eight
if( (reinterpret_cast<uintptr_t>(ptr) & 0x7UL) != 0UL ) ///< SCA MISRA-C++:2008 Justified Rule 5-2-9
{ ///< UT Justified Branch: HW dependency
ptr = NULLPTR;
}
return ptr;
}
/**
* @brief Tests memory.
*
* @todo normal type casts should be done.
*
* @param addr Memory address pointer.
* @param size Size in byte.
* @return True if test complete.
*/
static bool_t isMemoryAvailable(void* const addr, size_t const size)
{
size_t mask( static_cast<ucell_t>(-1) );
ucell_t* ptr( reinterpret_cast<ucell_t*>(addr) ); ///< SCA MISRA-C++:2008 Justified Rule 5-2-8
// Value test
for( size_t i(0UL); i<size; i++)
{
ptr[i] = static_cast<ucell_t>(i & mask);
}
for( size_t i(0UL); i<size; i++)
{
if(ptr[i] != static_cast<ucell_t>(i & mask))
{ ///< UT Justified Branch: HW dependency
return false;
}
}
// 0x55 test
for( size_t i(0UL); i<size; i++)
{
ptr[i] = static_cast<ucell_t>(0x55555555UL & mask);
}
for( size_t i(0UL); i<size; i++)
{
if(ptr[i] != static_cast<ucell_t>(0x55555555UL & mask))
{ ///< UT Justified Branch: HW dependency
return false;
}
}
// 0xAA test
for( size_t i(0UL); i<size; i++)
{
ptr[i] = static_cast<ucell_t>(0xAAAAAAAAUL & mask);
}
for( size_t i(0UL); i<size; i++)
{
if(ptr[i] != static_cast<ucell_t>(0xAAAAAAAAUL & mask))
{ ///< UT Justified Branch: HW dependency
return false;
}
}
// Zero test
for( size_t i(0UL); i<size; i++)
{
ptr[i] = 0x00U;
}
for( size_t i(0UL); i<size; i++)
{
if(ptr[i] != 0x00U)
{ ///< UT Justified Branch: HW dependency
return false;
}
}
return true;
}
/**
* @copydoc eoos::Object::Object(Object const&)
*/
Heap(Heap const&); ///< SCA MISRA-C++:2008 Justified Rule 3-2-2 and Rule 3-2-4
/**
* @copydoc eoos::Object::operator=(Object const&)
*/
Heap& operator=(Heap const&); ///< SCA MISRA-C++:2008 Justified Rule 3-2-2 and Rule 3-2-4
#if EOOS_CPP_STANDARD >= 2011
/**
* @copydoc eoos::Object::Object(Object&&)
*/
Heap(Heap&&) noexcept = delete;
/**
* @copydoc eoos::Object::operator=(Object&&)
*/
Heap& operator=(Heap&&) & noexcept = delete;
#endif // EOOS_CPP_STANDARD >= 2011
/**
* @class NoAllocator
* @brief No allocator for creating MutexGuard on stack.
*/
class NoAllocator
{
public:
/**
* @copydoc eoos::lib::Allocator::allocate(size_t)
*/
static void* allocate(size_t)
{
return NULLPTR;
}
/**
* @copydoc eoos::lib::Allocator::allocate(size_t).
*/
static void free(void*) ///< UT Justified Branch: Language dependency
{
}
};
/**
* @struct Aligner<S>
* @brief Heap class aligner aligns that to eight.
*
* @note If given S is already multiple 8, the class size will be 8 bytes.
*
* @tparam S Size of Heap class.
*/
template <size_t S>
struct Aligner
{
public:
/**
* @brief Constructor.
*/
Aligner()
{
#ifdef EOOS_DEBUG
for(size_t i(0U); i<SIZE; i++)
{
val_[i] = 0x0AUL;
}
#endif
}
private:
/**
* @brief Aligning data size.
*/
static const size_t SIZEOF = S;
/**
* @brief Aligning data size.
*/
static const size_t MASK = ~0x7UL;
/**
* @brief Aligning data size.
*/
static const size_t SIZE = ( ( SIZEOF & MASK ) + 0x8UL ) - SIZEOF;
/**
* @brief Temp array.
*/
ucell_t val_[SIZE];
};
/**
* @class VirtualTable
* @brief Contains a Virtual Function Table only.
*
* Probably, the solution of using this empty class
* is not delicate, but it works for understanding
* about size of a virtual function table of this Heap class.
*
* @note This uint64_t variable of the class is used, because some compilers
* might put 64 bit variable to aligned 8 memory address. Therefore, size of classes
* with 32 bit pointer to virtual table and one 64 bit variable is 16 bytes.
*/
class VirtualTable : public api::Heap{uint64_t temp;};
/**
* @class HeapBlock
* @brief Heap memory block.
*
* The class data has to be aligned to 8.
*/
class HeapBlock
{
public:
/**
* @brief Constructor.
*
* @param heap Pointer to heap class.
* @param size Size of byte given to this new block.
*/
HeapBlock(api::Heap* heap, size_t size)
: heap_(heap)
, prev_(NULLPTR)
, next_(NULLPTR)
, attr_(0)
, size_(size - sizeof(HeapBlock))
, key_(BLOCK_KEY) {
}
/**
* @brief Destructor.
*/
~HeapBlock()
{
}
/**
* @brief Tests if this object has been constructed.
*
* @return True if object has been constructed successfully.
*/
bool_t isConstructed() const
{
return (key_ == BLOCK_KEY) ? true : false;
}
/**
* @brief Allocates a memory block.
*
* @param size Size in byte.
* @return Pointer to an allocated memory.
*/
void* alloc(size_t size)
{
if(size == 0UL)
{
return NULLPTR;
}
// Align a size to 8 byte boudary
if((size & 0x7UL) != 0UL)
{
size = (size & ~0x7UL) + 0x8UL;
}
HeapBlock* curr( this );
while(curr != NULLPTR)
{
if(curr->isUsed() || (curr->size_ < size) )
{
curr = curr->next_;
}
else
{
break;
}
}
if(curr == NULLPTR)
{
return NULLPTR;
}
// Has required memory size for data and a new heap block
if( curr->size_ >= (size + sizeof(HeapBlock)) )
{
HeapBlock* next( new ( curr->next(size) ) HeapBlock(heap_, curr->size_ - size) );
if(next == NULLPTR)
{ ///< UT Justified Branch: HW dependency
return NULLPTR;
}
next->next_ = curr->next_;
next->prev_ = curr;
if(next->next_ != NULLPTR)
{
next->next_->prev_ = next;
}
curr->next_ = next;
curr->size_ = size;
}
curr->attr_ |= ATTR_USED;
return curr->data();
}
/**
* @brief Frees allocated memory by this block.
*/
void free()
{
if( !canDelete() )
{ ///< UT Justified Branch: HW dependency
return;
}
uint32_t sibling( 0UL );
if( prev_ != NULLPTR )
{
if( !prev_->isUsed() )
{
sibling |= PREV_FREE;
}
}
if( next_ != NULLPTR )
{
if( !next_->isUsed() )
{
sibling |= NEXT_FREE;
}
}
switch(sibling)
{
case PREV_FREE | NEXT_FREE:
{
prev_->size_ += ( 2UL * sizeof(HeapBlock) ) + size_ + next_->size_;
prev_->next_ = next_->next_;
if(prev_->next_ != NULLPTR)
{
prev_->next_->prev_ = prev_;
}
break;
}
case PREV_FREE:
{
prev_->size_ += sizeof(HeapBlock) + size_;
prev_->next_ = next_;
if(next_ != NULLPTR)
{
next_->prev_ = prev_;
}
break;
}
case NEXT_FREE:
{
size_ += sizeof(HeapBlock) + next_->size_;
next_ = next_->next_;
if(next_ != NULLPTR)
{
next_->prev_ = this;
}
attr_ &= MASK_UNUSED;
break;
}
default:
{
attr_ &= MASK_UNUSED;
break;
}
}
}
/**
* @brief Operator new.
*
* @param size Unused.
* @param ptr Address of memory.
* @return Address of memory.
*/
static void* operator new(size_t, void* const ptr)
{
void* memory( NULLPTR );
do
{
// Size of this class must be multipled to eight
if((sizeof(HeapBlock) & 0x7UL) != 0UL)
{ ///< UT Justified Branch: HW dependency
break;
}
// The passed address must be multipled to eight
if((reinterpret_cast<uintptr_t>(ptr) & 0x7UL) != 0UL) ///< SCA MISRA-C++:2008 Justified Rule 5-2-9
{ ///< UT Justified Branch: HW dependency
break;
}
memory = ptr;
}
while(false);
return memory;
}
/**
* @brief Operator delete.
*/
static void operator delete(void*, void*) {} ///< UT Justified Branch: Language dependency
private:
/**
* @brief Tests if this memory block is available for deleting.
*
* @return True if it may be deleted.
*/
bool_t canDelete() const
{
if( !isConstructed() )
{ ///< UT Justified Branch: HW dependency
return false;
}
if( !heap_->isConstructed() )
{ ///< UT Justified Branch: HW dependency
return false;
}
return true;
}
/**
* @brief Tests if this memory block is available.
*
* @return True if memory block is available.
*/
bool_t isUsed() const
{
return ( (attr_ & ATTR_USED) != 0UL ) ? true : false;
}
/**
* @brief Returns an address to data of this block.
*
* @return Pointer to memory.
*/
void* data()
{
uintptr_t const addr( reinterpret_cast<uintptr_t>(this) + sizeof(HeapBlock) ); ///< SCA MISRA-C++:2008 Justified Rule 5-2-9
return reinterpret_cast<void*>(addr); ///< SCA MISRA-C++:2008 Justified Rule 5-2-8
}
/**
* @brief Returns an address to next block.
*
* @return PSinter to memory.
*/
void* next(size_t const size)
{
uintptr_t const addr( reinterpret_cast<uintptr_t>(this) + sizeof(HeapBlock) + size ); ///< SCA MISRA-C++:2008 Justified Rule 5-2-9
return reinterpret_cast<void*>(addr); ///< SCA MISRA-C++:2008 Justified Rule 5-2-8
}
/**
* @copydoc eoos::Object::Object(Object const&)
*/
HeapBlock(HeapBlock const&); ///< SCA MISRA-C++:2008 Justified Rule 3-2-2 and Rule 3-2-4
/**
* @copydoc eoos::Object::operator=(Object const&)
*/
HeapBlock& operator=(HeapBlock const&); ///< SCA MISRA-C++:2008 Justified Rule 3-2-2 and Rule 3-2-4
#if EOOS_CPP_STANDARD >= 2011
/**
* @copydoc eoos::Object::Object(Object&&)
*/
HeapBlock(HeapBlock&&) noexcept = delete;
/**
* @copydoc eoos::Object::operator=(Object&&)
*/
HeapBlock& operator=(HeapBlock&&) & noexcept = delete;
#endif // EOOS_CPP_STANDARD >= 2011
/**
* @brief Heap block definition key.
*/
static const size_t BLOCK_KEY = 0x20140515UL;
/**
* @brief Block is used.
*/
static const uint32_t ATTR_USED = 0x00000001UL;
/**
* @brief Next block is free.
*/
static const uint32_t NEXT_FREE = 0x00000001UL;
/**
* @brief Previous block is free.
*/
static const uint32_t PREV_FREE = 0x00000002UL;
/**
* @brief Mask block is unused.
*/
static const uint32_t MASK_UNUSED = 0xFFFFFFFEUL;
/**
* @brief Heap page of this block.
*/
api::Heap* heap_;
/**
* @brief Next block.
*/
HeapBlock* prev_;
/**
* @brief Previous block.
*/
HeapBlock* next_;
/**
* @brief Attributes of this block.
*/
uint32_t attr_;
/**
* @brief Size in byte of this block.
*/
size_t size_;
/**
* @brief Heap block definition key.
*/
size_t key_;
};
/**
* @struct HeapData
* @brief Heap data.
*
* This structure is needed for aligning heap data or otherwise
* this Heap class can not de aligned because it is incompleted.
*/
struct HeapData
{
/**
* @brief Constructor.
*
* @param isize Total heap size.
* @param mutex A mutex to protect memory allocation.
*/
HeapData(size_t isize, api::Mutex& imutex)
: block(NULLPTR)
, mutex(&imutex)
, size(0)
, key(HEAP_KEY) {
size = (isize & ~0x7UL) - sizeof(Heap);
}
/**
* @brief First memory block of heap page memory.
*/
HeapBlock* block; ///< SCA MISRA-C++:2008 Justified Rule 11-0-1
/**
* @brief Thread allocation protection.
*/
api::Mutex* mutex; ///< SCA MISRA-C++:2008 Justified Rule 11-0-1
/**
* @brief Actual size of heap.
*/
size_t size; ///< SCA MISRA-C++:2008 Justified Rule 11-0-1
/**
* @brief Heap page memory definition key.
*/
int32_t key; ///< SCA MISRA-C++:2008 Justified Rule 11-0-1
private:
/**
* @copydoc eoos::Object::Object(Object const&)
*/
HeapData(HeapData const&); ///< SCA MISRA-C++:2008 Justified Rule 3-2-2 and Rule 3-2-4
/**
* @copydoc eoos::Object::operator=(Object const&)
*/
HeapData& operator=(HeapData const&); ///< SCA MISRA-C++:2008 Justified Rule 3-2-2 and Rule 3-2-4
#if EOOS_CPP_STANDARD >= 2011
/**
* @copydoc eoos::Object::Object(Object&&)
*/
HeapData(HeapData&&) noexcept = delete;
/**
* @copydoc eoos::Object::operator=(Object&&)
*/
HeapData& operator=(HeapData&&) & noexcept = delete;
#endif // EOOS_CPP_STANDARD >= 2011
};
/**
* @brief Size of this Heap class without aligned data.
*/
static const size_t SIZEOF_HEAP = ( sizeof(HeapData) + sizeof(VirtualTable) ) - sizeof(uint64_t);
/**
* @brief Heap page memory definition key.
*/
static const int32_t HEAP_KEY = 0x19820401;
/**
* @brief Data of this heap.
*/
HeapData data_;
/**
* @brief Aligning data.
*/
Aligner<SIZEOF_HEAP> temp_;
};
} // namespace lib
} // namespace eoos
#endif // LIB_HEAP_HPP_