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

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