dali/internal/common/fixed-size-memory-pool.cpp

   1 /*
   2  * Copyright (c) 2015 Samsung Electronics Co., Ltd.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  *
  16  */
  17
  18 // CLASS HEADER
  19 #include <dali/internal/common/fixed-size-memory-pool.h>
  20
  21 // INTERNAL HEADERS
  22 #include <dali/devel-api/threading/mutex.h>
  23 #include <dali/public-api/common/dali-common.h>
  24 #include <dali/public-api/common/vector-wrapper.h>
  25 #include <cmath>
  26
  27 namespace Dali
  28 {
  29 namespace Internal
  30 {
  31 /**
  32  * @brief Private implementation class
  33  */
  34 struct FixedSizeMemoryPool::Impl
  35 {
  36   /**
  37    * @brief Struct to represent a block of memory from which allocations can be made.
  38    *
  39    * The block forms a linked list.
  40    */
  41   struct Block
  42   {
  43     void*    blockMemory; ///< The allocated memory from which allocations can be made
  44     Block*   nextBlock;   ///< The next block in the linked list
  45     SizeType mBlockSize;  ///< Size of the block in bytes
  46
  47     /**
  48      * @brief Construct a new block with given size
  49      *
  50      * @param size The size of the memory block to allocate in bytes. Must be non-zero.
  51      */
  52     Block(SizeType size)
  53     : nextBlock(nullptr),
  54       mBlockSize(size)
  55     {
  56       blockMemory = ::operator new(size);
  57       DALI_ASSERT_ALWAYS(blockMemory && "Out of memory");
  58     }
  59
  60     /**
  61      * @brief Destructor
  62      */
  63     ~Block()
  64     {
  65       ::operator delete(blockMemory);
  66     }
  67
  68   private:
  69     // Undefined
  70     Block(const Block& block);
  71
  72     // Undefined
  73     Block& operator=(const Block& block);
  74   };
  75
  76   /**
  77    * @brief Constructor
  78    */
  79   Impl(SizeType fixedSize, SizeType initialCapacity, SizeType maximumBlockCapacity, SizeType maximumBlockCount)
  80   : mMutex(),
  81     mFixedSize(fixedSize),
  82     mMemoryBlocks(initialCapacity * mFixedSize),
  83     mMaximumBlockCapacity(maximumBlockCapacity),
  84     mCurrentBlock(&mMemoryBlocks),
  85     mCurrentBlockCapacity(initialCapacity),
  86     mCurrentBlockSize(0),
  87     mMaximumBlockCount(maximumBlockCount),
  88     mDeletedObjects(nullptr)
  89   {
  90     // We need enough room to store the deleted list in the data
  91     DALI_ASSERT_DEBUG(mFixedSize >= sizeof(void*));
  92
  93     if(mMaximumBlockCount < 0xffffffff)
  94     {
  95       // Only use mBlocks for key/ptr conversion with max number of blocks
  96       mBlocks.reserve(32);
  97       mBlocks.push_back(&mMemoryBlocks);
  98
  99       // Compute masks and shifts
 100       int bitCount = (logf(mMaximumBlockCount) / logf(2.0f)) + 1;
 101       mBlockShift  = 32 - bitCount;
 102       mBlockIdMask = ((0x01 << bitCount) - 1) << mBlockShift;
 103       mIndexMask   = ~mBlockIdMask;
 104     }
 105   }
 106
 107   /**
 108    * @brief Destructor
 109    */
 110   ~Impl()
 111   {
 112     // Clean up memory block linked list (mMemoryBlocks will be auto-destroyed by its destructor)
 113     Block* block = mMemoryBlocks.nextBlock;
 114     while(block)
 115     {
 116       Block* nextBlock = block->nextBlock;
 117       delete block;
 118       block = nextBlock;
 119     }
 120   }
 121
 122   /**
 123    * @brief Allocate a new block for allocating memory from
 124    */
 125   void AllocateNewBlock()
 126   {
 127     // Double capacity for the new block
 128     SizeType size = mCurrentBlockCapacity * 2;
 129     if(size > mMaximumBlockCapacity || size < mCurrentBlockCapacity) // Check for overflow of size type
 130     {
 131       size = mMaximumBlockCapacity;
 132     }
 133
 134     mCurrentBlockCapacity = size;
 135
 136     // Allocate
 137     Block* block             = new Block(mCurrentBlockCapacity * mFixedSize);
 138     mCurrentBlock->nextBlock = block; // Add to end of linked list
 139     mCurrentBlock            = block;
 140
 141     mCurrentBlockSize = 0;
 142
 143     // Add to main list of blocks
 144     if(mBlockShift)
 145     {
 146       mBlocks.push_back(block);
 147     }
 148   }
 149 #ifdef DEBUG_ENABLED
 150
 151   /**
 152    * @brief check the memory being free'd exists inside the memory pool
 153    * @param[in] memory address of object to remove
 154    */
 155   void CheckMemoryIsInsidePool(const void* const memory)
 156   {
 157     bool         inRange = false;
 158     const Block* block   = &mMemoryBlocks;
 159
 160     while(block)
 161     {
 162       const void* const endOfBlock = reinterpret_cast<char*>(block->blockMemory) + block->mBlockSize;
 163
 164       if((memory >= block->blockMemory) && (memory < (endOfBlock)))
 165       {
 166         inRange = true;
 167         break;
 168       }
 169       block = block->nextBlock;
 170     }
 171     DALI_ASSERT_DEBUG(inRange && "Freeing memory that does not exist in memory pool");
 172   }
 173 #endif
 174
 175   Mutex mMutex; ///< Mutex for thread-safe allocation and deallocation
 176
 177   SizeType mFixedSize; ///< The size of each allocation in bytes
 178
 179   Block    mMemoryBlocks;         ///< Linked list of allocated memory blocks
 180   SizeType mMaximumBlockCapacity; ///< The maximum allowed capacity of allocations in a new memory block
 181
 182   std::vector<Block*> mBlocks; ///< Address of each allocated block
 183
 184   Block*   mCurrentBlock;         ///< Pointer to the active block
 185   SizeType mCurrentBlockCapacity; ///< The maximum number of allocations that can be allocated for the current block
 186   SizeType mCurrentBlockSize;     ///< The number of allocations allocated to the current block
 187
 188   SizeType mMaximumBlockCount{0xffffffff}; ///< Maximum number of blocks (or unlimited)
 189   SizeType mBlockShift{0x0};               ///< number of bits to shift block id in key
 190   SizeType mBlockIdMask{0x0};              ///< mask for key conversion
 191   SizeType mIndexMask{0xffffffff};         ///< mask for key conversion
 192
 193   void* mDeletedObjects; ///< Pointer to the head of the list of deleted objects. The addresses are stored in the allocated memory blocks.
 194 };
 195
 196 FixedSizeMemoryPool::FixedSizeMemoryPool(
 197   SizeType fixedSize,
 198   SizeType initialCapacity,
 199   SizeType maximumBlockCapacity,
 200   SizeType maximumBlockCount)
 201 {
 202   mImpl = new Impl(fixedSize, initialCapacity, maximumBlockCapacity, maximumBlockCount);
 203 }
 204
 205 FixedSizeMemoryPool::~FixedSizeMemoryPool()
 206 {
 207   delete mImpl;
 208 }
 209
 210 void* FixedSizeMemoryPool::Allocate()
 211 {
 212   // First, recycle deleted objects
 213   if(mImpl->mDeletedObjects)
 214   {
 215     void* recycled         = mImpl->mDeletedObjects;
 216     mImpl->mDeletedObjects = *(reinterpret_cast<void**>(mImpl->mDeletedObjects)); // Pop head off front of deleted objects list
 217     return recycled;
 218   }
 219
 220   // Check if current block is full
 221   if(mImpl->mCurrentBlockSize >= mImpl->mCurrentBlockCapacity)
 222   {
 223     mImpl->AllocateNewBlock();
 224   }
 225
 226   // Placement new the object in block memory
 227   uint8_t* objectAddress = static_cast<uint8_t*>(mImpl->mCurrentBlock->blockMemory);
 228   objectAddress += mImpl->mCurrentBlockSize * mImpl->mFixedSize;
 229   mImpl->mCurrentBlockSize++;
 230
 231   return objectAddress;
 232 }
 233
 234 void FixedSizeMemoryPool::Free(void* memory)
 235 {
 236   if(memory)
 237   {
 238 #ifdef DEBUG_ENABLED
 239     mImpl->CheckMemoryIsInsidePool(memory);
 240 #endif
 241
 242     // Add memory to head of deleted objects list. Store next address in the same memory space as the old object.
 243     *(reinterpret_cast<void**>(memory)) = mImpl->mDeletedObjects;
 244     mImpl->mDeletedObjects              = memory;
 245   }
 246 }
 247
 248 void* FixedSizeMemoryPool::AllocateThreadSafe()
 249 {
 250   Mutex::ScopedLock lock(mImpl->mMutex);
 251   return Allocate();
 252 }
 253
 254 void FixedSizeMemoryPool::FreeThreadSafe(void* memory)
 255 {
 256   if(memory)
 257   {
 258     Mutex::ScopedLock lock(mImpl->mMutex);
 259     Free(memory);
 260   }
 261 }
 262
 263 void* FixedSizeMemoryPool::GetPtrFromKey(FixedSizeMemoryPool::KeyType key)
 264 {
 265 #if defined(__LP64__)
 266   uint32_t blockId{0u};
 267   uint32_t index = key & mImpl->mIndexMask;
 268
 269   if(DALI_LIKELY(mImpl->mBlockShift)) // Key contains block id & index within block
 270   {
 271     blockId = (key & mImpl->mBlockIdMask) >> mImpl->mBlockShift;
 272     if(blockId < mImpl->mBlocks.size())
 273     {
 274       return static_cast<uint8_t*>(mImpl->mBlocks[blockId]->blockMemory) + mImpl->mFixedSize * index;
 275     }
 276     return nullptr;
 277   }
 278   else
 279   {
 280     // Treat as having no block id, and search for Nth item
 281     Impl::Block* block = &mImpl->mMemoryBlocks;
 282     while(block != nullptr)
 283     {
 284       const SizeType numberOfItems = (block->mBlockSize) / mImpl->mFixedSize;
 285       if(index < numberOfItems)
 286       {
 287         return static_cast<uint8_t*>(block->blockMemory) + mImpl->mFixedSize * index;
 288       }
 289       index -= numberOfItems;
 290       block = block->nextBlock;
 291     }
 292   }
 293   return nullptr;
 294 #else
 295   // Treat ptrs as keys
 296   return static_cast<void*>(key);
 297 #endif
 298 }
 299
 300 FixedSizeMemoryPool::KeyType FixedSizeMemoryPool::GetKeyFromPtr(void* ptr)
 301 {
 302 #if defined(__LP64__)
 303   uint32_t blockId = 0;
 304   uint32_t index   = 0;
 305   bool     found   = false;
 306
 307   // If block count is limited, the bit shift is non-zero.
 308   if(DALI_LIKELY(mImpl->mBlockShift))
 309   {
 310     for(auto block : mImpl->mBlocks)
 311     {
 312       const void* const endOfBlock = reinterpret_cast<char*>(block->blockMemory) + block->mBlockSize;
 313
 314       if(block->blockMemory <= ptr && ptr < endOfBlock)
 315       {
 316         index = (static_cast<uint8_t*>(ptr) - static_cast<uint8_t*>(block->blockMemory)) / mImpl->mFixedSize;
 317         found = true;
 318         break;
 319       }
 320       ++blockId;
 321     }
 322   }
 323   else
 324   {
 325     // Block count is unlimited, key is item count. But, potentially have to iterate through many blocks.
 326     Impl::Block* block = &mImpl->mMemoryBlocks;
 327     while(block != nullptr && !found)
 328     {
 329       const void* const endOfBlock = reinterpret_cast<char*>(block->blockMemory) + block->mBlockSize;
 330
 331       if(block->blockMemory <= ptr && ptr < endOfBlock)
 332       {
 333         index += (static_cast<uint8_t*>(ptr) - static_cast<uint8_t*>(block->blockMemory)) / mImpl->mFixedSize;
 334         found = true;
 335         break;
 336       }
 337       index += block->mBlockSize / mImpl->mFixedSize;
 338       block = block->nextBlock;
 339     }
 340   }
 341   if(found)
 342   {
 343     return blockId << mImpl->mBlockShift | (index & mImpl->mIndexMask);
 344   }
 345
 346   return -1;
 347 #else
 348   return static_cast<FixedSizeMemoryPool::KeyType>(ptr);
 349 #endif
 350 }
 351
 352 uint32_t FixedSizeMemoryPool::GetCapacity() const
 353 {
 354   // Ignores deleted objects list, just returns currently allocated size
 355   uint32_t totalAllocation = 0;
 356 #ifdef DEBUG_ENABLED
 357   Mutex::ScopedLock lock(mImpl->mMutex);
 358   Impl::Block*      block = &mImpl->mMemoryBlocks;
 359   while(block)
 360   {
 361     totalAllocation += block->mBlockSize;
 362     block = block->nextBlock;
 363   }
 364 #endif
 365   return totalAllocation;
 366 }
 367
 368 } // namespace Internal
 369
 370 } // namespace Dali