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 #if defined(__LP64__)
  46     KeyType mIndexOffset; ///< The Offset of this block's index
  47 #endif
  48     SizeType mBlockSize; ///< Size of the block in bytes
  49
  50     /**
  51      * @brief Construct a new block with given size
  52      *
  53      * @param size The size of the memory block to allocate in bytes. Must be non-zero.
  54      */
  55     Block(SizeType size)
  56     : nextBlock(nullptr),
  57 #if defined(__LP64__)
  58       mIndexOffset(0),
  59 #endif
  60       mBlockSize(size)
  61     {
  62       blockMemory = ::operator new(size);
  63       DALI_ASSERT_ALWAYS(blockMemory && "Out of memory");
  64     }
  65
  66     /**
  67      * @brief Destructor
  68      */
  69     ~Block()
  70     {
  71       ::operator delete(blockMemory);
  72     }
  73
  74   private:
  75     // Undefined
  76     Block(const Block& block);
  77
  78     // Undefined
  79     Block& operator=(const Block& block);
  80   };
  81
  82   /**
  83    * @brief Constructor
  84    */
  85   Impl(SizeType fixedSize, SizeType initialCapacity, SizeType maximumBlockCapacity, SizeType maximumBlockCount)
  86   : mMutex(),
  87     mFixedSize(fixedSize),
  88     mMemoryBlocks(initialCapacity * mFixedSize),
  89     mMaximumBlockCapacity(maximumBlockCapacity),
  90     mCurrentBlock(&mMemoryBlocks),
  91     mCurrentBlockCapacity(initialCapacity),
  92     mCurrentBlockSize(0),
  93     mMaximumBlockCount(maximumBlockCount),
  94     mDeletedObjects(nullptr)
  95   {
  96     // We need enough room to store the deleted list in the data
  97     DALI_ASSERT_DEBUG(mFixedSize >= sizeof(void*));
  98
  99 #if defined(__LP64__)
 100     if(mMaximumBlockCount < 0xffffffff)
 101     {
 102       // Only use mBlocks for key/ptr conversion with max number of blocks
 103       mBlocks.reserve(32);
 104       mBlocks.push_back(&mMemoryBlocks);
 105
 106       // Compute masks and shifts
 107       int bitCount = (logf(mMaximumBlockCount) / logf(2.0f)) + 1;
 108       mBlockShift  = 32 - bitCount;
 109       mBlockIdMask = ((0x01 << bitCount) - 1) << mBlockShift;
 110       mIndexMask   = ~mBlockIdMask;
 111     }
 112 #endif
 113   }
 114
 115   /**
 116    * @brief Destructor
 117    */
 118   ~Impl()
 119   {
 120     // Clean up memory block linked list (mMemoryBlocks will be auto-destroyed by its destructor)
 121     Block* block = mMemoryBlocks.nextBlock;
 122     while(block)
 123     {
 124       Block* nextBlock = block->nextBlock;
 125       delete block;
 126       block = nextBlock;
 127     }
 128   }
 129
 130   /**
 131    * @brief Allocate a new block for allocating memory from
 132    */
 133   void AllocateNewBlock()
 134   {
 135     // Double capacity for the new block
 136     SizeType size = mCurrentBlockCapacity * 2;
 137     if(size > mMaximumBlockCapacity || size < mCurrentBlockCapacity) // Check for overflow of size type
 138     {
 139       size = mMaximumBlockCapacity;
 140     }
 141
 142     mCurrentBlockCapacity = size;
 143
 144     // Allocate
 145     Block* block = new Block(mCurrentBlockCapacity * mFixedSize);
 146
 147 #if defined(__LP64__)
 148     if(mBlockShift) // Key contains block id & index within block
 149     {
 150       // Add to main list of blocks
 151       mBlocks.push_back(block);
 152 #endif
 153       mCurrentBlock->nextBlock = block; // Add end of linked list
 154       mCurrentBlock            = block;
 155 #if defined(__LP64__)
 156     }
 157     else
 158     {
 159       // Heuristic optimization. Make bigger block positioned at front, instead of header.
 160       // (Since change the Block value might be heavy)
 161       if(mCurrentBlock == &mMemoryBlocks)
 162       {
 163         block->mIndexOffset = mMemoryBlocks.mBlockSize / mFixedSize;
 164
 165         // Add to end of linked list.
 166         // Now mCurrentBlock is next block of header.
 167         mCurrentBlock->nextBlock = block;
 168         mCurrentBlock            = block;
 169       }
 170       else
 171       {
 172         block->mIndexOffset = mCurrentBlock->mIndexOffset + (mCurrentBlock->mBlockSize / mFixedSize);
 173
 174         // Add new block as next of header.
 175         mMemoryBlocks.nextBlock = block;
 176
 177         // Make previous mCurrentBlock as next of new block.
 178         block->nextBlock = mCurrentBlock;
 179
 180         // Keep mCurrentBlock is next block of mMemoryBlocks.
 181         mCurrentBlock = block;
 182       }
 183     }
 184 #endif
 185
 186     mCurrentBlockSize = 0;
 187   }
 188 #ifdef DEBUG_ENABLED
 189
 190   /**
 191    * @brief check the memory being free'd exists inside the memory pool
 192    * @param[in] memory address of object to remove
 193    */
 194   void CheckMemoryIsInsidePool(const void* const memory)
 195   {
 196     bool         inRange = false;
 197     const Block* block   = &mMemoryBlocks;
 198
 199     while(block)
 200     {
 201       const void* const endOfBlock = reinterpret_cast<char*>(block->blockMemory) + block->mBlockSize;
 202
 203       if((memory >= block->blockMemory) && (memory < (endOfBlock)))
 204       {
 205         inRange = true;
 206         break;
 207       }
 208       block = block->nextBlock;
 209     }
 210     DALI_ASSERT_DEBUG(inRange && "Freeing memory that does not exist in memory pool");
 211   }
 212 #endif
 213
 214   Mutex mMutex; ///< Mutex for thread-safe allocation and deallocation
 215
 216   SizeType mFixedSize; ///< The size of each allocation in bytes
 217
 218   Block    mMemoryBlocks;         ///< Linked list of allocated memory blocks
 219   SizeType mMaximumBlockCapacity; ///< The maximum allowed capacity of allocations in a new memory block
 220
 221 #if defined(__LP64__)
 222   std::vector<Block*> mBlocks; ///< Address of each allocated block
 223 #endif
 224
 225   Block*   mCurrentBlock;         ///< Pointer to the active block
 226   SizeType mCurrentBlockCapacity; ///< The maximum number of allocations that can be allocated for the current block
 227   SizeType mCurrentBlockSize;     ///< The number of allocations allocated to the current block
 228
 229   SizeType mMaximumBlockCount{0xffffffff}; ///< Maximum number of blocks (or unlimited)
 230 #if defined(__LP64__)
 231   SizeType mBlockShift{0x0};       ///< number of bits to shift block id in key
 232   SizeType mBlockIdMask{0x0};      ///< mask for key conversion
 233   SizeType mIndexMask{0xffffffff}; ///< mask for key conversion
 234 #endif
 235
 236   void* mDeletedObjects; ///< Pointer to the head of the list of deleted objects. The addresses are stored in the allocated memory blocks.
 237 };
 238
 239 FixedSizeMemoryPool::FixedSizeMemoryPool(
 240   SizeType fixedSize,
 241   SizeType initialCapacity,
 242   SizeType maximumBlockCapacity,
 243   SizeType maximumBlockCount)
 244 {
 245   mImpl = new Impl(fixedSize, initialCapacity, maximumBlockCapacity, maximumBlockCount);
 246 }
 247
 248 FixedSizeMemoryPool::~FixedSizeMemoryPool()
 249 {
 250   delete mImpl;
 251 }
 252
 253 void* FixedSizeMemoryPool::Allocate()
 254 {
 255   // First, recycle deleted objects
 256   if(mImpl->mDeletedObjects)
 257   {
 258     void* recycled         = mImpl->mDeletedObjects;
 259     mImpl->mDeletedObjects = *(reinterpret_cast<void**>(mImpl->mDeletedObjects)); // Pop head off front of deleted objects list
 260     return recycled;
 261   }
 262
 263   // Check if current block is full
 264   if(mImpl->mCurrentBlockSize >= mImpl->mCurrentBlockCapacity)
 265   {
 266     mImpl->AllocateNewBlock();
 267   }
 268
 269   // Placement new the object in block memory
 270   uint8_t* objectAddress = static_cast<uint8_t*>(mImpl->mCurrentBlock->blockMemory);
 271   objectAddress += mImpl->mCurrentBlockSize * mImpl->mFixedSize;
 272   mImpl->mCurrentBlockSize++;
 273
 274   return objectAddress;
 275 }
 276
 277 void FixedSizeMemoryPool::Free(void* memory)
 278 {
 279   if(memory)
 280   {
 281 #ifdef DEBUG_ENABLED
 282     mImpl->CheckMemoryIsInsidePool(memory);
 283 #endif
 284
 285     // Add memory to head of deleted objects list. Store next address in the same memory space as the old object.
 286     *(reinterpret_cast<void**>(memory)) = mImpl->mDeletedObjects;
 287     mImpl->mDeletedObjects              = memory;
 288   }
 289 }
 290
 291 void* FixedSizeMemoryPool::AllocateThreadSafe()
 292 {
 293   Mutex::ScopedLock lock(mImpl->mMutex);
 294   return Allocate();
 295 }
 296
 297 void FixedSizeMemoryPool::FreeThreadSafe(void* memory)
 298 {
 299   if(memory)
 300   {
 301     Mutex::ScopedLock lock(mImpl->mMutex);
 302     Free(memory);
 303   }
 304 }
 305
 306 void* FixedSizeMemoryPool::GetPtrFromKey(FixedSizeMemoryPool::KeyType key)
 307 {
 308 #if defined(__LP64__)
 309   uint32_t blockId{0u};
 310   uint32_t index = key & mImpl->mIndexMask;
 311
 312   if(DALI_LIKELY(mImpl->mBlockShift)) // Key contains block id & index within block
 313   {
 314     blockId = (key & mImpl->mBlockIdMask) >> mImpl->mBlockShift;
 315     if(blockId < mImpl->mBlocks.size())
 316     {
 317       return static_cast<uint8_t*>(mImpl->mBlocks[blockId]->blockMemory) + mImpl->mFixedSize * index;
 318     }
 319     return nullptr;
 320   }
 321   else
 322   {
 323     // Treat as having no block id, and search for Nth item
 324     Impl::Block* block = &mImpl->mMemoryBlocks;
 325     while(block != nullptr)
 326     {
 327       const uint32_t indexOffset   = block->mIndexOffset;
 328       const SizeType numberOfItems = (block->mBlockSize) / mImpl->mFixedSize;
 329       if(indexOffset <= index && index < indexOffset + numberOfItems)
 330       {
 331         return static_cast<uint8_t*>(block->blockMemory) + mImpl->mFixedSize * (index - indexOffset);
 332       }
 333       block = block->nextBlock;
 334     }
 335   }
 336   return nullptr;
 337 #else
 338   // Treat ptrs as keys
 339   return static_cast<void*>(key);
 340 #endif
 341 }
 342
 343 FixedSizeMemoryPool::KeyType FixedSizeMemoryPool::GetKeyFromPtr(void* ptr)
 344 {
 345 #if defined(__LP64__)
 346   uint32_t blockId = 0;
 347   uint32_t index   = 0;
 348   bool     found   = false;
 349
 350   // If block count is limited, the bit shift is non-zero.
 351   if(DALI_LIKELY(mImpl->mBlockShift))
 352   {
 353     // Iterate backward so we can search at bigger blocks first.
 354     blockId = mImpl->mBlocks.size();
 355     for(auto iter = mImpl->mBlocks.rbegin(), iterEnd = mImpl->mBlocks.rend(); iter != iterEnd; ++iter)
 356     {
 357       --blockId;
 358       auto* block = *iter;
 359
 360       const void* const endOfBlock = reinterpret_cast<char*>(block->blockMemory) + block->mBlockSize;
 361
 362       if(block->blockMemory <= ptr && ptr < endOfBlock)
 363       {
 364         index = (static_cast<uint8_t*>(ptr) - static_cast<uint8_t*>(block->blockMemory)) / mImpl->mFixedSize;
 365         found = true;
 366         break;
 367       }
 368     }
 369   }
 370   else
 371   {
 372     // Block count is unlimited, key is item count. But, potentially have to iterate through many blocks.
 373     Impl::Block* block = &mImpl->mMemoryBlocks;
 374     while(block != nullptr && !found)
 375     {
 376       const void* const endOfBlock = reinterpret_cast<char*>(block->blockMemory) + block->mBlockSize;
 377
 378       if(block->blockMemory <= ptr && ptr < endOfBlock)
 379       {
 380         index = block->mIndexOffset + (static_cast<uint8_t*>(ptr) - static_cast<uint8_t*>(block->blockMemory)) / mImpl->mFixedSize;
 381         found = true;
 382         break;
 383       }
 384       block = block->nextBlock;
 385     }
 386   }
 387   if(found)
 388   {
 389     return blockId << mImpl->mBlockShift | (index & mImpl->mIndexMask);
 390   }
 391
 392   return -1;
 393 #else
 394   return static_cast<FixedSizeMemoryPool::KeyType>(ptr);
 395 #endif
 396 }
 397
 398 uint32_t FixedSizeMemoryPool::GetCapacity() const
 399 {
 400   // Ignores deleted objects list, just returns currently allocated size
 401   uint32_t totalAllocation = 0;
 402 #ifdef DEBUG_ENABLED
 403   Mutex::ScopedLock lock(mImpl->mMutex);
 404   Impl::Block*      block = &mImpl->mMemoryBlocks;
 405   while(block)
 406   {
 407     totalAllocation += block->mBlockSize;
 408     block = block->nextBlock;
 409   }
 410 #endif
 411   return totalAllocation;
 412 }
 413
 414 } // namespace Internal
 415
 416 } // namespace Dali