framework/delibs/depool/deMemPool.c

   1 /*-------------------------------------------------------------------------
   2  * drawElements Memory Pool Library
   3  * --------------------------------
   4  *
   5  * Copyright 2014 The Android Open Source Project
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  *      http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  *
  19  *//*!
  20  * \file
  21  * \brief Memory pool management.
  22  *//*--------------------------------------------------------------------*/
  23
  24 #include "deMemPool.h"
  25 #include "deMemory.h"
  26 #include "deInt32.h"
  27
  28 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
  29 #       include "deRandom.h"
  30 #endif
  31
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 enum
  36 {
  37         INITIAL_PAGE_SIZE               = 128,          /*!< Size for the first allocated memory page.                  */
  38         MAX_PAGE_SIZE                   = 8096,         /*!< Maximum size for a memory page.                                    */
  39         MEM_PAGE_BASE_ALIGN             = 4                     /*!< Base alignment guarantee for mem page data ptr.    */
  40 };
  41
  42 typedef struct MemPage_s MemPage;
  43
  44 /*--------------------------------------------------------------------*//*!
  45  * \internal
  46  * \brief Memory page header.
  47  *
  48  * Represent a page of memory allocate by a memory pool.
  49  *//*--------------------------------------------------------------------*/
  50 struct MemPage_s
  51 {
  52         int                     capacity;
  53         int                     bytesAllocated;
  54
  55         MemPage*        nextPage;
  56 };
  57
  58 #if defined(DE_SUPPORT_DEBUG_POOLS)
  59 typedef struct DebugAlloc_s DebugAlloc;
  60
  61 struct DebugAlloc_s
  62 {
  63         void*                   memPtr;
  64         DebugAlloc*             next;
  65 };
  66 #endif
  67
  68 /*--------------------------------------------------------------------*//*!
  69  * \brief Memory pool.
  70  *
  71  * A pool of memory from which individual memory allocations can be made.
  72  * The memory pools don't have a freeing operation for individual allocations,
  73  * but rather all of the memory allocated from a pool is freed when the pool
  74  * is destroyed.
  75  *
  76  * The pools can be arranged into a hierarchy. If a pool with children is
  77  * destroyed, all of the children are first recursively destroyed and then
  78  * the pool itself.
  79  *
  80  * The memory pools support a feature where individual allocations can be
  81  * made to simulate failure (i.e., return null). This can be enabled by
  82  * creating the root pool with the deMemPool_createFailingRoot() function.
  83  * When the feature is enabled, also creation of sub-pools occasionally
  84  * fails.
  85  *//*--------------------------------------------------------------------*/
  86 struct deMemPool_s
  87 {
  88         deUint32                flags;                          /*!< Flags.                                                                                     */
  89         deMemPool*              parent;                         /*!< Pointer to parent (null for root pools).           */
  90         deMemPoolUtil*  util;                           /*!< Utilities (callbacks etc.).                                        */
  91         int                             numChildren;            /*!< Number of child pools.                                                     */
  92         deMemPool*              firstChild;                     /*!< Pointer to first child pool in linked list.        */
  93         deMemPool*              prevPool;                       /*!< Previous pool in parent's linked list.                     */
  94         deMemPool*              nextPool;                       /*!< Next pool in parent's linked list.                         */
  95
  96         MemPage*                currentPage;            /*!< Current memory page from which to allocate.        */
  97
  98 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
  99         deBool                  allowFailing;           /*!< Is allocation failure simulation enabled?          */
 100         deRandom                failRandom;                     /*!< RNG for failing allocations.                                       */
 101 #endif
 102 #if defined(DE_SUPPORT_DEBUG_POOLS)
 103         deBool                  enableDebugAllocs;      /*!< If true, always allocates using deMalloc().        */
 104         DebugAlloc*             debugAllocListHead;     /*!< List of allocation in debug mode.                          */
 105
 106         int                             lastAllocatedIndex;     /*!< Index of last allocated pool (rootPool only).      */
 107         int                             allocIndex;                     /*!< Allocation index (running counter).                        */
 108 #endif
 109 #if defined(DE_SUPPORT_POOL_MEMORY_TRACKING)
 110         int                             maxMemoryAllocated;     /*!< Maximum amount of memory allocated from pools.     */
 111         int                             maxMemoryCapacity;      /*!< Maximum amount of memory allocated for pools.      */
 112 #endif
 113 };
 114
 115 /*--------------------------------------------------------------------*//*!
 116  * \internal
 117  * \brief Initialize a memory page.
 118  * \param page          Memory page to initialize.
 119  * \param capacity      Capacity allocated for the memory page.
 120  *//*--------------------------------------------------------------------*/
 121 static void MemPage_init (MemPage* page, size_t capacity)
 122 {
 123         memset(page, 0, sizeof(MemPage));
 124 #if defined(DE_DEBUG)
 125         memset(page + 1, 0xCD, capacity);
 126 #endif
 127         page->capacity = (int)capacity;
 128 }
 129
 130 /*--------------------------------------------------------------------*//*!
 131  * \internal
 132  * \brief Create a new memory page.
 133  * \param capacity      Capacity for the memory page.
 134  * \return The created memory page (or null on failure).
 135  *//*--------------------------------------------------------------------*/
 136 static MemPage* MemPage_create (size_t capacity)
 137 {
 138         MemPage* page = (MemPage*)deMalloc(sizeof(MemPage) + capacity);
 139         if (!page)
 140                 return DE_NULL;
 141
 142         DE_ASSERT(deIsAlignedPtr(page+1, MEM_PAGE_BASE_ALIGN));
 143
 144         MemPage_init(page, capacity);
 145         return page;
 146 }
 147
 148 /*--------------------------------------------------------------------*//*!
 149  * \internal
 150  * \brief Destroy a memory page.
 151  * \param page  Memory page to destroy.
 152  *//*--------------------------------------------------------------------*/
 153 static void MemPage_destroy (MemPage* page)
 154 {
 155 #if defined(DE_DEBUG)
 156         /* Fill with garbage to hopefully catch dangling pointer bugs easier. */
 157         deUint8* dataPtr = (deUint8*)(page + 1);
 158         memset(dataPtr, 0xCD, (size_t)page->capacity);
 159 #endif
 160         deFree(page);
 161 }
 162
 163 /*--------------------------------------------------------------------*//*!
 164  * \internal
 165  * \brief Internal function for creating a new memory pool.
 166  * \param parent        Parent pool (may be null).
 167  * \return The created memory pool (or null on failure).
 168  *//*--------------------------------------------------------------------*/
 169 static deMemPool* createPoolInternal (deMemPool* parent)
 170 {
 171         deMemPool*      pool;
 172         MemPage*        initialPage;
 173
 174 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
 175         if (parent && parent->allowFailing)
 176         {
 177                 if ((deRandom_getUint32(&parent->failRandom) & 16383) <= 15)
 178                         return DE_NULL;
 179         }
 180 #endif
 181
 182         /* Init first page. */
 183         initialPage = MemPage_create(INITIAL_PAGE_SIZE);
 184         if (!initialPage)
 185                 return DE_NULL;
 186
 187         /* Alloc pool from initial page. */
 188         DE_ASSERT((int)sizeof(deMemPool) <= initialPage->capacity);
 189         pool = (deMemPool*)(initialPage + 1);
 190         initialPage->bytesAllocated += (int)sizeof(deMemPool);
 191
 192         memset(pool, 0, sizeof(deMemPool));
 193         pool->currentPage = initialPage;
 194
 195         /* Register to parent. */
 196         pool->parent = parent;
 197         if (parent)
 198         {
 199                 parent->numChildren++;
 200                 if (parent->firstChild) parent->firstChild->prevPool = pool;
 201                 pool->nextPool = parent->firstChild;
 202                 parent->firstChild = pool;
 203         }
 204
 205         /* Get utils from parent. */
 206         pool->util = parent ? parent->util : DE_NULL;
 207
 208 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
 209         pool->allowFailing = parent ? parent->allowFailing : DE_FALSE;
 210         deRandom_init(&pool->failRandom, parent ? deRandom_getUint32(&parent->failRandom) : 0x1234abcd);
 211 #endif
 212
 213 #if defined(DE_SUPPORT_DEBUG_POOLS)
 214         pool->enableDebugAllocs         = parent ? parent->enableDebugAllocs : DE_FALSE;
 215         pool->debugAllocListHead        = DE_NULL;
 216
 217         /* Pool allocation index. */
 218         {
 219                 deMemPool* root = pool;
 220                 while (root->parent)
 221                         root = root->parent;
 222
 223                 if (pool == root)
 224                         root->lastAllocatedIndex = 0;
 225
 226                 pool->allocIndex = ++root->lastAllocatedIndex;
 227
 228                 /* \note Put the index of leaking pool here and add a breakpoint to catch leaks easily. */
 229 /*              if (pool->allocIndex == 51)
 230                         root = root;*/
 231         }
 232 #endif
 233
 234         return pool;
 235 }
 236
 237 /*--------------------------------------------------------------------*//*!
 238  * \brief Create a new root memory pool.
 239  * \return The created memory pool (or null on failure).
 240  *//*--------------------------------------------------------------------*/
 241 deMemPool* deMemPool_createRoot (const deMemPoolUtil* util, deUint32 flags)
 242 {
 243         deMemPool* pool = createPoolInternal(DE_NULL);
 244         if (!pool)
 245                 return DE_NULL;
 246 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
 247         if (flags & DE_MEMPOOL_ENABLE_FAILING_ALLOCS)
 248                 pool->allowFailing = DE_TRUE;
 249 #endif
 250 #if defined(DE_SUPPORT_DEBUG_POOLS)
 251         if (flags & DE_MEMPOOL_ENABLE_DEBUG_ALLOCS)
 252         {
 253                 pool->enableDebugAllocs         = DE_TRUE;
 254                 pool->debugAllocListHead        = DE_NULL;
 255         }
 256 #endif
 257         DE_UNREF(flags); /* in case no debug features enabled */
 258
 259         /* Get copy of utilities. */
 260         if (util)
 261         {
 262                 deMemPoolUtil* utilCopy = DE_POOL_NEW(pool, deMemPoolUtil);
 263                 DE_ASSERT(util->allocFailCallback);
 264                 if (!utilCopy)
 265                 {
 266                         deMemPool_destroy(pool);
 267                         return DE_NULL;
 268                 }
 269
 270                 memcpy(utilCopy, util, sizeof(deMemPoolUtil));
 271                 pool->util = utilCopy;
 272         }
 273
 274         return pool;
 275 }
 276
 277 /*--------------------------------------------------------------------*//*!
 278  * \brief Create a sub-pool for an existing memory pool.
 279  * \return The created memory pool (or null on failure).
 280  *//*--------------------------------------------------------------------*/
 281 deMemPool* deMemPool_create (deMemPool* parent)
 282 {
 283         deMemPool* pool;
 284         DE_ASSERT(parent);
 285         pool = createPoolInternal(parent);
 286         if (!pool && parent->util)
 287                 parent->util->allocFailCallback(parent->util->userPointer);
 288         return pool;
 289 }
 290
 291 /*--------------------------------------------------------------------*//*!
 292  * \brief Destroy a memory pool.
 293  * \param pool  Pool to be destroyed.
 294  *
 295  * Frees all the memory allocated from the pool. Also destroyed any child
 296  * pools that the pool has (recursively).
 297  *//*--------------------------------------------------------------------*/
 298 void deMemPool_destroy (deMemPool* pool)
 299 {
 300         deMemPool* iter;
 301         deMemPool* iterNext;
 302
 303 #if defined(DE_SUPPORT_POOL_MEMORY_TRACKING)
 304         /* Update memory consumption statistics. */
 305         if (pool->parent)
 306         {
 307                 deMemPool* root = pool->parent;
 308                 while (root->parent)
 309                         root = root->parent;
 310                 root->maxMemoryAllocated        = deMax32(root->maxMemoryAllocated, deMemPool_getNumAllocatedBytes(root, DE_TRUE));
 311                 root->maxMemoryCapacity         = deMax32(root->maxMemoryCapacity, deMemPool_getCapacity(root, DE_TRUE));
 312         }
 313 #endif
 314
 315         /* Destroy all children. */
 316         iter = pool->firstChild;
 317         while (iter)
 318         {
 319                 iterNext = iter->nextPool;
 320                 deMemPool_destroy(iter);
 321                 iter = iterNext;
 322         }
 323
 324         DE_ASSERT(pool->numChildren == 0);
 325
 326         /* Update pointers. */
 327         if (pool->prevPool) pool->prevPool->nextPool = pool->nextPool;
 328         if (pool->nextPool) pool->nextPool->prevPool = pool->prevPool;
 329
 330         if (pool->parent)
 331         {
 332                 deMemPool* parent = pool->parent;
 333                 if (parent->firstChild == pool)
 334                         parent->firstChild = pool->nextPool;
 335
 336                 parent->numChildren--;
 337                 DE_ASSERT(parent->numChildren >= 0);
 338         }
 339
 340 #if defined(DE_SUPPORT_DEBUG_POOLS)
 341         /* Free all debug allocations. */
 342         if (pool->enableDebugAllocs)
 343         {
 344                 DebugAlloc* alloc       = pool->debugAllocListHead;
 345                 DebugAlloc* next;
 346
 347                 while (alloc)
 348                 {
 349                         next = alloc->next;
 350                         deAlignedFree(alloc->memPtr);
 351                         deFree(alloc);
 352                         alloc = next;
 353                 }
 354
 355                 pool->debugAllocListHead = DE_NULL;
 356         }
 357 #endif
 358
 359         /* Free pages. */
 360         /* \note Pool itself is allocated from first page, so we must not touch the pool after freeing the page! */
 361         {
 362                 MemPage* page = pool->currentPage;
 363                 MemPage* nextPage;
 364
 365                 while (page)
 366                 {
 367                         nextPage = page->nextPage;
 368                         MemPage_destroy(page);
 369                         page = nextPage;
 370                 }
 371         }
 372 }
 373
 374 /*--------------------------------------------------------------------*//*!
 375  * \brief Get the number of children for a pool.
 376  * \return The number of (immediate) child pools a memory pool has.
 377  *//*--------------------------------------------------------------------*/
 378 int deMemPool_getNumChildren (const deMemPool* pool)
 379 {
 380         return pool->numChildren;
 381 }
 382
 383 /*--------------------------------------------------------------------*//*!
 384  * \brief Get the number of bytes allocated (by the user) from the pool.
 385  * \param pool          Pool pointer.
 386  * \param recurse       Is operation recursive to child pools?
 387  * \return The number of bytes allocated by the pool (including child pools
 388  *                 if 'recurse' is true).
 389  *//*--------------------------------------------------------------------*/
 390 int deMemPool_getNumAllocatedBytes (const deMemPool* pool, deBool recurse)
 391 {
 392         int                     numAllocatedBytes = 0;
 393         MemPage*        memPage;
 394
 395         for (memPage = pool->currentPage; memPage; memPage = memPage->nextPage)
 396                 numAllocatedBytes += memPage->bytesAllocated;
 397
 398         if (recurse)
 399         {
 400                 deMemPool* child;
 401                 for (child = pool->firstChild; child; child = child->nextPool)
 402                         numAllocatedBytes += deMemPool_getNumAllocatedBytes(child, DE_TRUE);
 403         }
 404
 405         return numAllocatedBytes;
 406 }
 407
 408 int deMemPool_getCapacity (const deMemPool* pool, deBool recurse)
 409 {
 410         int                     numCapacityBytes = 0;
 411         MemPage*        memPage;
 412
 413         for (memPage = pool->currentPage; memPage; memPage = memPage->nextPage)
 414                 numCapacityBytes += memPage->capacity;
 415
 416         if (recurse)
 417         {
 418                 deMemPool* child;
 419                 for (child = pool->firstChild; child; child = child->nextPool)
 420                         numCapacityBytes += deMemPool_getCapacity(child, DE_TRUE);
 421         }
 422
 423         return numCapacityBytes;
 424 }
 425
 426 DE_INLINE void* deMemPool_allocInternal (deMemPool* pool, size_t numBytes, deUint32 alignBytes)
 427 {
 428         MemPage* curPage = pool->currentPage;
 429
 430 #if defined(DE_SUPPORT_FAILING_POOL_ALLOC)
 431         if (pool->allowFailing)
 432         {
 433                 if ((deRandom_getUint32(&pool->failRandom) & 16383) <= 15)
 434                         return DE_NULL;
 435         }
 436 #endif
 437
 438 #if defined(DE_SUPPORT_DEBUG_POOLS)
 439         if (pool->enableDebugAllocs)
 440         {
 441                 DebugAlloc*     header  = DE_NEW(DebugAlloc);
 442                 void*           ptr             = deAlignedMalloc(numBytes, alignBytes);
 443
 444                 if (!header || !ptr)
 445                 {
 446                         deFree(header);
 447                         deAlignedFree(ptr);
 448                         return DE_NULL;
 449                 }
 450
 451                 header->memPtr  = ptr;
 452                 header->next    = pool->debugAllocListHead;
 453                 pool->debugAllocListHead = header;
 454
 455                 return ptr;
 456         }
 457 #endif
 458
 459         DE_ASSERT(curPage);
 460         DE_ASSERT(deIsPowerOfTwo32((int)alignBytes));
 461         {
 462                 void*   curPagePtr              = (void*)((deUint8*)(curPage + 1) + curPage->bytesAllocated);
 463                 void*   alignedPtr              = deAlignPtr(curPagePtr, alignBytes);
 464                 size_t  alignPadding    = (size_t)((deUintptr)alignedPtr - (deUintptr)curPagePtr);
 465
 466                 if (numBytes + alignPadding > (size_t)(curPage->capacity - curPage->bytesAllocated))
 467                 {
 468                         /* Does not fit to current page. */
 469                         int             maxAlignPadding         = deMax32(0, ((int)alignBytes)-MEM_PAGE_BASE_ALIGN);
 470                         int             newPageCapacity         = deMax32(deMin32(2*curPage->capacity, MAX_PAGE_SIZE), ((int)numBytes)+maxAlignPadding);
 471
 472                         curPage = MemPage_create((size_t)newPageCapacity);
 473                         if (!curPage)
 474                                 return DE_NULL;
 475
 476                         curPage->nextPage       = pool->currentPage;
 477                         pool->currentPage       = curPage;
 478
 479                         DE_ASSERT(curPage->bytesAllocated == 0);
 480
 481                         curPagePtr                      = (void*)(curPage + 1);
 482                         alignedPtr                      = deAlignPtr(curPagePtr, alignBytes);
 483                         alignPadding            = (size_t)((deUintptr)alignedPtr - (deUintptr)curPagePtr);
 484
 485                         DE_ASSERT(numBytes + alignPadding <= (size_t)curPage->capacity);
 486                 }
 487
 488                 curPage->bytesAllocated += (int)(numBytes + alignPadding);
 489                 return alignedPtr;
 490         }
 491 }
 492
 493 /*--------------------------------------------------------------------*//*!
 494  * \brief Allocate memory from a pool.
 495  * \param pool          Memory pool to allocate from.
 496  * \param numBytes      Number of bytes to allocate.
 497  * \return Pointer to the allocate memory (or null on failure).
 498  *//*--------------------------------------------------------------------*/
 499 void* deMemPool_alloc (deMemPool* pool, size_t numBytes)
 500 {
 501         void* ptr;
 502         DE_ASSERT(pool);
 503         DE_ASSERT(numBytes > 0);
 504         ptr = deMemPool_allocInternal(pool, numBytes, DE_POOL_DEFAULT_ALLOC_ALIGNMENT);
 505         if (!ptr && pool->util)
 506                 pool->util->allocFailCallback(pool->util->userPointer);
 507         return ptr;
 508 }
 509
 510 /*--------------------------------------------------------------------*//*!
 511  * \brief Allocate aligned memory from a pool.
 512  * \param pool                  Memory pool to allocate from.
 513  * \param numBytes              Number of bytes to allocate.
 514  * \param alignBytes    Required alignment in bytes, must be power of two.
 515  * \return Pointer to the allocate memory (or null on failure).
 516  *//*--------------------------------------------------------------------*/
 517 void* deMemPool_alignedAlloc (deMemPool* pool, size_t numBytes, deUint32 alignBytes)
 518 {
 519         void* ptr;
 520         DE_ASSERT(pool);
 521         DE_ASSERT(numBytes > 0);
 522         DE_ASSERT(deIsPowerOfTwo32((int)alignBytes));
 523         ptr = deMemPool_allocInternal(pool, numBytes, alignBytes);
 524         DE_ASSERT(deIsAlignedPtr(ptr, alignBytes));
 525         if (!ptr && pool->util)
 526                 pool->util->allocFailCallback(pool->util->userPointer);
 527         return ptr;
 528 }
 529
 530 /*--------------------------------------------------------------------*//*!
 531  * \brief Duplicate a piece of memory into a memory pool.
 532  * \param pool  Memory pool to allocate from.
 533  * \param ptr   Piece of memory to duplicate.
 534  * \return Pointer to the copied memory block (or null on failure).
 535  *//*--------------------------------------------------------------------*/
 536 void* deMemPool_memDup (deMemPool* pool, const void* ptr, size_t numBytes)
 537 {
 538         void* newPtr = deMemPool_alloc(pool, numBytes);
 539         if (newPtr)
 540                 memcpy(newPtr, ptr, numBytes);
 541         return newPtr;
 542 }
 543
 544 /*--------------------------------------------------------------------*//*!
 545  * \brief Duplicate a string into a memory pool.
 546  * \param pool  Memory pool to allocate from.
 547  * \param str   String to duplicate.
 548  * \return Pointer to the new string (or null on failure).
 549  *//*--------------------------------------------------------------------*/
 550 char* deMemPool_strDup (deMemPool* pool, const char* str)
 551 {
 552         size_t  len             = strlen(str);
 553         char*   newStr  = (char*)deMemPool_alloc(pool, len+1);
 554         if (newStr)
 555                 memcpy(newStr, str, len+1);
 556         return newStr;
 557 }
 558
 559 /*--------------------------------------------------------------------*//*!
 560  * \brief Duplicate a string into a memory pool, with a maximum length.
 561  * \param pool          Memory pool to allocate from.
 562  * \param str           String to duplicate.
 563  * \param maxLength     Maximum number of characters to duplicate.
 564  * \return Pointer to the new string (or null on failure).
 565  *//*--------------------------------------------------------------------*/
 566 char* deMemPool_strnDup (deMemPool* pool, const char* str, int maxLength)
 567 {
 568         size_t  len                     = (size_t)deMin32((int)strlen(str), deMax32(0, maxLength));
 569         char*   newStr          = (char*)deMemPool_alloc(pool, len + 1);
 570
 571         DE_ASSERT(maxLength >= 0);
 572
 573         if (newStr)
 574         {
 575                 memcpy(newStr, str, len);
 576                 newStr[len] = 0;
 577         }
 578         return newStr;
 579 }
 580
 581 #if defined(DE_SUPPORT_POOL_MEMORY_TRACKING)
 582
 583 int deMemPool_getMaxNumAllocatedBytes (const deMemPool* pool)
 584 {
 585         DE_ASSERT(pool && !pool->parent); /* must be root */
 586         return deMax32(pool->maxMemoryAllocated, deMemPool_getNumAllocatedBytes(pool, DE_TRUE));
 587 }
 588
 589 int deMemPool_getMaxCapacity (const deMemPool* pool)
 590 {
 591         DE_ASSERT(pool && !pool->parent); /* must be root */
 592         return deMax32(pool->maxMemoryCapacity, deMemPool_getCapacity(pool, DE_TRUE));
 593 }
 594
 595 #endif