X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=dali%2Finternal%2Fcommon%2Ffixed-size-memory-pool.cpp;h=44e0fd35fabe39bc0156de91a64739226eafaf9c;hb=e4d22de85c81987aa749fb21dca87e88ed170509;hp=8b691936deace7e1c3fc5100223a250b8e8c13d4;hpb=54dff6a35a504884c076a370b660ed9a0a6c6bdb;p=platform%2Fcore%2Fuifw%2Fdali-core.git diff --git a/dali/internal/common/fixed-size-memory-pool.cpp b/dali/internal/common/fixed-size-memory-pool.cpp index 8b69193..44e0fd3 100644 --- a/dali/internal/common/fixed-size-memory-pool.cpp +++ b/dali/internal/common/fixed-size-memory-pool.cpp @@ -19,14 +19,15 @@ #include // INTERNAL HEADERS +#include #include +#include +#include namespace Dali { - namespace Internal { - /** * @brief Private implementation class */ @@ -39,19 +40,27 @@ struct FixedSizeMemoryPool::Impl */ struct Block { - void* blockMemory; ///< The allocated memory from which allocations can be made - Block* nextBlock; ///< The next block in the linked list + void* blockMemory; ///< The allocated memory from which allocations can be made + Block* nextBlock; ///< The next block in the linked list +#if defined(__LP64__) + KeyType mIndexOffset; ///< The Offset of this block's index +#endif + SizeType mBlockSize; ///< Size of the block in bytes /** * @brief Construct a new block with given size * * @param size The size of the memory block to allocate in bytes. Must be non-zero. */ - Block( SizeType size ) - : nextBlock( NULL ) + Block(SizeType size) + : nextBlock(nullptr), +#if defined(__LP64__) + mIndexOffset(0), +#endif + mBlockSize(size) { - blockMemory = ::operator new( size ); - DALI_ASSERT_ALWAYS( blockMemory && "Out of memory" ); + blockMemory = ::operator new(size); + DALI_ASSERT_ALWAYS(blockMemory && "Out of memory"); } /** @@ -59,31 +68,48 @@ struct FixedSizeMemoryPool::Impl */ ~Block() { - ::operator delete( blockMemory ); + ::operator delete(blockMemory); } private: // Undefined - Block( const Block& block ); + Block(const Block& block); // Undefined - Block& operator=( const Block& block ); + Block& operator=(const Block& block); }; /** * @brief Constructor */ - Impl( SizeType fixedSize, SizeType initialCapacity, SizeType maximumBlockCapacity ) - : mFixedSize( fixedSize ), - mMemoryBlocks( initialCapacity * mFixedSize ), - mMaximumBlockCapacity( maximumBlockCapacity ), - mCurrentBlock( &mMemoryBlocks ), - mCurrentBlockCapacity( initialCapacity ), - mCurrentBlockSize( 0 ), - mDeletedObjects( NULL ) + Impl(SizeType fixedSize, SizeType initialCapacity, SizeType maximumBlockCapacity, SizeType maximumBlockCount) + : mMutex(), + mFixedSize(fixedSize), + mMemoryBlocks(initialCapacity * mFixedSize), + mMaximumBlockCapacity(maximumBlockCapacity), + mCurrentBlock(&mMemoryBlocks), + mCurrentBlockCapacity(initialCapacity), + mCurrentBlockSize(0), + mMaximumBlockCount(maximumBlockCount), + mDeletedObjects(nullptr) { // We need enough room to store the deleted list in the data - DALI_ASSERT_DEBUG( mFixedSize >= sizeof( void* ) ); + DALI_ASSERT_DEBUG(mFixedSize >= sizeof(void*)); + +#if defined(__LP64__) + if(mMaximumBlockCount < 0xffffffff) + { + // Only use mBlocks for key/ptr conversion with max number of blocks + mBlocks.reserve(32); + mBlocks.push_back(&mMemoryBlocks); + + // Compute masks and shifts + int bitCount = (logf(mMaximumBlockCount) / logf(2.0f)) + 1; + mBlockShift = 32 - bitCount; + mBlockIdMask = ((0x01 << bitCount) - 1) << mBlockShift; + mIndexMask = ~mBlockIdMask; + } +#endif } /** @@ -93,7 +119,7 @@ struct FixedSizeMemoryPool::Impl { // Clean up memory block linked list (mMemoryBlocks will be auto-destroyed by its destructor) Block* block = mMemoryBlocks.nextBlock; - while( block ) + while(block) { Block* nextBlock = block->nextBlock; delete block; @@ -108,7 +134,7 @@ struct FixedSizeMemoryPool::Impl { // Double capacity for the new block SizeType size = mCurrentBlockCapacity * 2; - if( size > mMaximumBlockCapacity || size < mCurrentBlockCapacity ) // Check for overflow of size type + if(size > mMaximumBlockCapacity || size < mCurrentBlockCapacity) // Check for overflow of size type { size = mMaximumBlockCapacity; } @@ -116,28 +142,107 @@ struct FixedSizeMemoryPool::Impl mCurrentBlockCapacity = size; // Allocate - Block* block = new Block( mCurrentBlockCapacity * mFixedSize ); - mCurrentBlock->nextBlock = block; // Add to end of linked list - mCurrentBlock = block; + Block* block = new Block(mCurrentBlockCapacity * mFixedSize); + +#if defined(__LP64__) + if(mBlockShift) // Key contains block id & index within block + { + // Add to main list of blocks + mBlocks.push_back(block); +#endif + mCurrentBlock->nextBlock = block; // Add end of linked list + mCurrentBlock = block; +#if defined(__LP64__) + } + else + { + // Heuristic optimization. Make bigger block positioned at front, instead of header. + // (Since change the Block value might be heavy) + if(mCurrentBlock == &mMemoryBlocks) + { + block->mIndexOffset = mMemoryBlocks.mBlockSize / mFixedSize; + + // Add to end of linked list. + // Now mCurrentBlock is next block of header. + mCurrentBlock->nextBlock = block; + mCurrentBlock = block; + } + else + { + block->mIndexOffset = mCurrentBlock->mIndexOffset + (mCurrentBlock->mBlockSize / mFixedSize); + + // Add new block as next of header. + mMemoryBlocks.nextBlock = block; + + // Make previous mCurrentBlock as next of new block. + block->nextBlock = mCurrentBlock; + + // Keep mCurrentBlock is next block of mMemoryBlocks. + mCurrentBlock = block; + } + } +#endif mCurrentBlockSize = 0; } +#ifdef DEBUG_ENABLED - SizeType mFixedSize; ///< The size of each allocation in bytes + /** + * @brief check the memory being free'd exists inside the memory pool + * @param[in] memory address of object to remove + */ + void CheckMemoryIsInsidePool(const void* const memory) + { + bool inRange = false; + const Block* block = &mMemoryBlocks; - Block mMemoryBlocks; ///< Linked list of allocated memory blocks - SizeType mMaximumBlockCapacity; ///< The maximum allowed capacity of allocations in a new memory block + while(block) + { + const void* const endOfBlock = reinterpret_cast(block->blockMemory) + block->mBlockSize; - Block* mCurrentBlock; ///< Pointer to the active block - SizeType mCurrentBlockCapacity; ///< The maximum number of allocations that can be allocated for the current block - SizeType mCurrentBlockSize; ///< The number of allocations allocated to the current block + if((memory >= block->blockMemory) && (memory < (endOfBlock))) + { + inRange = true; + break; + } + block = block->nextBlock; + } + DALI_ASSERT_DEBUG(inRange && "Freeing memory that does not exist in memory pool"); + } +#endif + + Mutex mMutex; ///< Mutex for thread-safe allocation and deallocation + + SizeType mFixedSize; ///< The size of each allocation in bytes + + Block mMemoryBlocks; ///< Linked list of allocated memory blocks + SizeType mMaximumBlockCapacity; ///< The maximum allowed capacity of allocations in a new memory block - void* mDeletedObjects; ///< Pointer to the head of the list of deleted objects. The addresses are stored in the allocated memory blocks. +#if defined(__LP64__) + std::vector mBlocks; ///< Address of each allocated block +#endif + + Block* mCurrentBlock; ///< Pointer to the active block + SizeType mCurrentBlockCapacity; ///< The maximum number of allocations that can be allocated for the current block + SizeType mCurrentBlockSize; ///< The number of allocations allocated to the current block + + SizeType mMaximumBlockCount{0xffffffff}; ///< Maximum number of blocks (or unlimited) +#if defined(__LP64__) + SizeType mBlockShift{0x0}; ///< number of bits to shift block id in key + SizeType mBlockIdMask{0x0}; ///< mask for key conversion + SizeType mIndexMask{0xffffffff}; ///< mask for key conversion +#endif + + void* mDeletedObjects; ///< Pointer to the head of the list of deleted objects. The addresses are stored in the allocated memory blocks. }; -FixedSizeMemoryPool::FixedSizeMemoryPool( SizeType fixedSize, SizeType initialCapacity, SizeType maximumBlockCapacity ) +FixedSizeMemoryPool::FixedSizeMemoryPool( + SizeType fixedSize, + SizeType initialCapacity, + SizeType maximumBlockCapacity, + SizeType maximumBlockCount) { - mImpl = new Impl( fixedSize, initialCapacity, maximumBlockCapacity ); + mImpl = new Impl(fixedSize, initialCapacity, maximumBlockCapacity, maximumBlockCount); } FixedSizeMemoryPool::~FixedSizeMemoryPool() @@ -148,32 +253,162 @@ FixedSizeMemoryPool::~FixedSizeMemoryPool() void* FixedSizeMemoryPool::Allocate() { // First, recycle deleted objects - if( mImpl->mDeletedObjects ) + if(mImpl->mDeletedObjects) { - void* recycled = mImpl->mDeletedObjects; - mImpl->mDeletedObjects = *( reinterpret_cast< void** >( mImpl->mDeletedObjects ) ); // Pop head off front of deleted objects list + void* recycled = mImpl->mDeletedObjects; + mImpl->mDeletedObjects = *(reinterpret_cast(mImpl->mDeletedObjects)); // Pop head off front of deleted objects list return recycled; } // Check if current block is full - if( mImpl->mCurrentBlockSize >= mImpl->mCurrentBlockCapacity ) + if(mImpl->mCurrentBlockSize >= mImpl->mCurrentBlockCapacity) { mImpl->AllocateNewBlock(); } // Placement new the object in block memory - unsigned char* objectAddress = static_cast< unsigned char* >( mImpl->mCurrentBlock->blockMemory ); + uint8_t* objectAddress = static_cast(mImpl->mCurrentBlock->blockMemory); objectAddress += mImpl->mCurrentBlockSize * mImpl->mFixedSize; mImpl->mCurrentBlockSize++; return objectAddress; } -void FixedSizeMemoryPool::Free( void* memory ) +void FixedSizeMemoryPool::Free(void* memory) +{ + if(memory) + { +#ifdef DEBUG_ENABLED + mImpl->CheckMemoryIsInsidePool(memory); +#endif + + // Add memory to head of deleted objects list. Store next address in the same memory space as the old object. + *(reinterpret_cast(memory)) = mImpl->mDeletedObjects; + mImpl->mDeletedObjects = memory; + } +} + +void* FixedSizeMemoryPool::AllocateThreadSafe() { - // Add memory to head of deleted objects list. Store next address in the same memory space as the old object. - *( reinterpret_cast< void** >( memory ) ) = mImpl->mDeletedObjects; - mImpl->mDeletedObjects = memory; + Mutex::ScopedLock lock(mImpl->mMutex); + return Allocate(); +} + +void FixedSizeMemoryPool::FreeThreadSafe(void* memory) +{ + if(memory) + { + Mutex::ScopedLock lock(mImpl->mMutex); + Free(memory); + } +} + +void* FixedSizeMemoryPool::GetPtrFromKey(FixedSizeMemoryPool::KeyType key) +{ +#if defined(__LP64__) + uint32_t blockId{0u}; + uint32_t index = key & mImpl->mIndexMask; + + if(DALI_LIKELY(mImpl->mBlockShift)) // Key contains block id & index within block + { + blockId = (key & mImpl->mBlockIdMask) >> mImpl->mBlockShift; + if(blockId < mImpl->mBlocks.size()) + { + return static_cast(mImpl->mBlocks[blockId]->blockMemory) + mImpl->mFixedSize * index; + } + return nullptr; + } + else + { + // Treat as having no block id, and search for Nth item + Impl::Block* block = &mImpl->mMemoryBlocks; + while(block != nullptr) + { + const uint32_t indexOffset = block->mIndexOffset; + const SizeType numberOfItems = (block->mBlockSize) / mImpl->mFixedSize; + if(indexOffset <= index && index < indexOffset + numberOfItems) + { + return static_cast(block->blockMemory) + mImpl->mFixedSize * (index - indexOffset); + } + block = block->nextBlock; + } + } + return nullptr; +#else + // Treat ptrs as keys + return static_cast(key); +#endif +} + +FixedSizeMemoryPool::KeyType FixedSizeMemoryPool::GetKeyFromPtr(void* ptr) +{ +#if defined(__LP64__) + uint32_t blockId = 0; + uint32_t index = 0; + bool found = false; + + // If block count is limited, the bit shift is non-zero. + if(DALI_LIKELY(mImpl->mBlockShift)) + { + // Iterate backward so we can search at bigger blocks first. + blockId = mImpl->mBlocks.size(); + for(auto iter = mImpl->mBlocks.rbegin(), iterEnd = mImpl->mBlocks.rend(); iter != iterEnd; ++iter) + { + --blockId; + auto* block = *iter; + + const void* const endOfBlock = reinterpret_cast(block->blockMemory) + block->mBlockSize; + + if(block->blockMemory <= ptr && ptr < endOfBlock) + { + index = (static_cast(ptr) - static_cast(block->blockMemory)) / mImpl->mFixedSize; + found = true; + break; + } + } + } + else + { + // Block count is unlimited, key is item count. But, potentially have to iterate through many blocks. + Impl::Block* block = &mImpl->mMemoryBlocks; + while(block != nullptr && !found) + { + const void* const endOfBlock = reinterpret_cast(block->blockMemory) + block->mBlockSize; + + if(block->blockMemory <= ptr && ptr < endOfBlock) + { + index = block->mIndexOffset + (static_cast(ptr) - static_cast(block->blockMemory)) / mImpl->mFixedSize; + found = true; + break; + } + block = block->nextBlock; + } + } + if(found) + { + return blockId << mImpl->mBlockShift | (index & mImpl->mIndexMask); + } + + return -1; +#else + return static_cast(ptr); +#endif +} + +uint32_t FixedSizeMemoryPool::GetCapacity() const +{ + // Ignores deleted objects list, just returns currently allocated size + uint32_t totalAllocation = 0; +#ifdef DEBUG_ENABLED + Mutex::ScopedLock lock(mImpl->mMutex); + Impl::Block* block = &mImpl->mMemoryBlocks; + while(block) + { + totalAllocation += block->mBlockSize; + block = block->nextBlock; + } +#endif + return totalAllocation; } } // namespace Internal